Найдите 2 недостающих числа в массиве целых чисел с двумя отсутствующими значениями

Ответ 1

Этот метод не рекомендуется, так как он страдает от проблем с переполнением integer. Поэтому используйте метод XOR, чтобы найти два числа, которые очень эффективны. Если вам интересно, я могу объяснить.

В соответствии с запросом @ordinary ниже я объясняю алгоритм:

ИЗМЕНИТЬ

Предположим, что максимальный элемент массива a[] равен B i.e предположим a[]={1,2,4}, и здесь 3 и 5 не присутствуют в [], поэтому максимальный элемент B=5.

• XOR все элементы массива a - X
• XOR все элементы от 1 до B до X
• найдите самый старший бит из X на x = x &(~(x-1));
• Теперь, если a[i] ^ x == x чем XOR a[i] до p else XOR с q
• Теперь для всех k от 1 до B, если k ^ x == x чем XOR с p else XOR с q
• Теперь напечатайте p и q

доказательство:

Пусть a = {1,2,4} и B равно 5, то есть от 1 до 5 недостающих чисел 3 и 5

Как только мы XOR элементы a и числа от 1 до 5, мы оставили с XOR 3 и 5, т.е. X.

Теперь, когда мы находим самый левый бит-набор из X, это не что иное, как самый левый бит между 3 и 5. (3--> 011, 5 --> 101 и x = 010 где x = 3 ^ 5)

После этого мы пытаемся разделить на две группы в соответствии с набором бит X, поэтому две группы будут:

p = 2 , 2 , 3 (all has the 2nd last bit set)

q = 1, 1, 4, 4, 5 (all has the 2nd last bit unset)

если мы XOR элементы p между собой, найдем 3 и аналогично, если мы XOR все элементы q между собой, чем получим 5. Отсюда и ответ.

код в java

public void findNumbers(int[] a, int B){
    int x=0;
    for(int i=0; i<a.length;i++){
        x=x^a[i];
    }
    for(int i=1;i<=B;i++){
        x=x^i;
    }
    x = x &(~(x-1));
    int p=0, q=0;
    for(int i=0;i<a.length;i++){
        if((a[i] & x) == x){
            p=p^a[i];
        }
        else{
            q=q^a[i];
        }   
    }
    for(int i=1;i<=B;i++){
        if((i & x) == x){
            p=p^i;
        }
        else{
            q=q^i;
        }
    }

    System.out.println("p: "+p+" : "+q);
}

Ответ 2

Пусть x и y - корни квадратного уравнения.

• Сумма корней, SUM= x + y
• Произведение корней, PRODUCT= x * y

Если мы знаем сумму и произведение, мы можем восстановить квадратичное уравнение как:

z^2 - (SUM)z + (PRODUCT) = 0

В упомянутом алгоритме мы найдем сумму и произведение, и из этого мы восстановим квадратичное уравнение, используя приведенную выше формулу.

Если вас интересует подробный вывод, вот ссылка. Прочитайте "Восстановление квадратичного уравнения из суммы и произведения корней" .

Ответ 3

У меня есть алгоритм для вышеуказанной проблемы.

Предположим, что

Actual Series: 1 2 3 4 5 6          a:sum=21 product= 720
Missing Number series: 1 * 3 4 * 6  b:sum=14 product= 72

a+b=21-14= 7 , ab=720/72=10

Теперь нам нужно найти a-b= sqrt[(a+b)^2 -4ab].

Если вы вычислите:

a-b= 3

Теперь

a+b=7
a-b=3

Добавьте оба уравнения:

2a=10, a=5

затем b=7-5=2, поэтому 2 и 5 отсутствуют.

Ответ 4

Начиная с

x+y == SUM
xy == PRODUCT

Есть два случая. Если PRODUCT равен нулю, то одно число 0, а другое - SUM. В противном случае оба значения не равны нулю; мы можем умножить первое уравнение на x без изменения равенства:

x*x + xy == x*SUM

Подставим второе уравнение:

x*x + PRODUCT = x*SUM

и переставить в обычном виде

x*x - x*SUM + PRODUCT = 0

Итак,

x = SUM/2 + sqrt(SUM*SUM - 4*PRODUCT)/2
y = SUM/2 - sqrt(SUM*SUM - 4*PRODUCT)/2

Ответ 5

Реализация Java: (на основе @Ben Voigt)

BigInteger fact=1;
int sum=0;
int prod=1;
int x,y; // The 2 missing numbers
int n=a.length;
int max=MIN_VALUE;

for (int i=0; i<a.length;i++){
  sum+=a[i]; //sums the existing numbers
  prod*=a[i]; //product the existing numbers
  if (max<a[i]) //searches for the biggest number in the array
     max=a[i];
}

while(max!=1){ //factorial for the maximum number
     fact*=max;
     max--;
}
sum=(n*(n+1))/2 - sum; //the sum of the 2 missing numbers
prod=fact/prod; //the product of the 2 missing numbers

x=sum/2 + Math.sqrt(sum*sum - 4*prod)/2;
y=sum/2 - Math.sqrt(sum*sum - 4*prod)/2;

Ответ 6

Below is the generic answer in java code for any number of missing numbers in a given array
//assumes that there are no duplicates
a = [1,2,3,4,5]
b = [1,2,5]
a-b=[3,4]

public list<integer> find(int[] input){
  int[] a= new int[] {1,2,3,4,5};//create a new array without missing numbers
  List<Integer> l = new ArrayList<Integer>();//list for missing numbers
  Map<Integer,Integer> m = new HashMap<Integer>();

  //populate a hashmap with the elements in the new array
  for(int i=0;i<input.length;i++){  
   m.put(input[i], 1);
  }
//loop through the given input array and check for missing numbers
 for(int i=0;i<a.length;i++){
  if (!m.contains(input[i]))
   l.add(input[i]);
}
 return l;
}

Ответ 7

Я надеюсь, что эта программа полезна всем вам, я взял ограничение до 10, это можно сделать так же, просто используйте n в качестве предела и выполните те же операции.

#include <iostream>
#include<math.h>

using namespace std;

int main()
{
    int i,x[100],sum1=0,sum2=0,prod1=1,prod2=1,k,j,p=0;
    cout<<"Enter 8 elements less than 10, they should be non recurring"<<endl;
    for(i=0;i<8;i++)
    {
        cin>>x[i];
    }
    sum1=((10)*(11))/2;
    for(i=0;i<8;i++)
    {
        sum2+=x[i];
    }
    k=sum1-sum2;
    for(i=1;i<10;i++)
    {
        prod1=prod1*i;
    }
    for(i=0;i<8;i++)
    {
        prod2=prod2*x[i];
    }
    j=prod1/prod2;
    p=sqrt((k*k)-(4*j));
    cout<<"One missing no:"<<p/2<<endl;
    cout<<"Second missing no:"<<k-p/2<<endl;


}

Ответ 8

#include <stdio.h>
#include <math.h>

/*
    the sum should be 1+...+n = n(n+1)/2
    the sum of squares should be 1^2+...+n^2 = n(n+1)(2n+1)/6.
*/

void find_missing_2_numbers(int *arr, int n);

int main()
{
    int arr[] = {3,7,1,6,8,5};

    find_missing_2_numbers(arr, 8);

    return 0;
}

void find_missing_2_numbers(int *arr, int n)
{

    int i, size, a, b, sum, sum_of_sqr, a_p_b, as_p_bs, a_i_b, a_m_b;
    size = n - 2;

    sum = 0;
    sum_of_sqr = 0;
    for (i = 0; i < size; i++)
    {
        sum += arr[i];
        sum_of_sqr += (arr[i] * arr[i]);
    }

    a_p_b = (n*(n+1))/2 - sum;
    as_p_bs = (n*(n+1)*(2 * n + 1))/6 - sum_of_sqr;
    a_i_b = ((a_p_b * a_p_b) - as_p_bs ) / 2;
    a_m_b = (int) sqrt((a_p_b * a_p_b) - 4 * a_i_b);
    a = (a_p_b + a_m_b) / 2;
    b = a_p_b - a;

    printf ("A: %d, B: %d\n", a, b);
}

Ответ 9

работает для любого количества недостающих элементов: Вы можете немного отформатировать код... но он также работает с дублирующимися и не дублирующимися записями:

public static void main(String args[] ) throws Exception {

        Scanner input = new Scanner(System.in);
        System.out.println("Enter no. of students in the class");
        int N = input.nextInt();
        List<Integer> l = new ArrayList<Integer>();
        int Nn=N;
        System.out.println("Enter the roll numbers");
        for(int i=0;i<Nn;i++)
        {
            int enter=input.nextInt();

            l.add(enter);      
        }
        Collections.sort(l);
        Integer listarr[]=new Integer[l.size()];
        listarr =l.toArray(listarr);


        int check=0;
        int m1[]=new int[N];
        for(int i=0;i<N;i++)
        {
            m1[i]=i+1;
        }

        for (int i = 0; i < N; i++) {
              boolean flag=false;

            {
                for (int j = 0; j < listarr.length; j++) {

                    if(m1[i]==listarr[j])
                    { 
                        flag=true;
                        break;

                    }
                    else
                    {

                    flag=false;

                    }
            }
                if(flag==false)
                {
                    System.out.println("Missing number Found : " + m1[i]);
                }

        }


    }

Ответ 10

public class MissingNumber{

static int[] array = { 1, 3, 5 };

public static void getMissingNumber() {

for (int i = 0; i < array.length; i++)
    System.out.println(array[i] + " ");

System.out.println("The Missing Number is:");
 int j = 0;
for (int i = 1; i <= 5; i++) {
    if (j < array.length && i == array[j])
    j++;
    else
    System.out.println(i + " ");
}

}
public static void main(String[] args) {
getMissingNumber();
}

}

Ответ 11

Пример кода (Java) для ответа @slider

 /**
     * get 2 missed numbers from randomly shuffled array of unique elements from [1,n]
     *
     * @param array - shuffled array of unique elements from [1,n], but 2 random elements was missed. len = n-2
     * @return array with 2 missed elements
     */
    public static int[] getMissedNumbers(int[] array) {

        int sum = 0;
        int fullSum = 0;
        int fullProduct = 1;
        int product = 1;
        for (int i = 0; i < array.length + 2; i++) {
            int currNaturalNumber = i + 1;
            fullSum = fullSum + currNaturalNumber;
            fullProduct = fullProduct * currNaturalNumber;

            if (i < array.length) {
                sum = sum + array[i];
                product = product * array[i];
            }
        }

        int missedSum = fullSum - sum; //firstMissedNum + secondMissedNum
        int missedProduct = fullProduct / product; //firstMissedNum * secondMissedNum

        //ax*x + bx + c = 0
        //x = (-b +- sqrt(b*b - 4*a*c))/2*a
        // -b = missedSum , c = missedProduct, a = 1
        Double firstMissedNum = (missedSum + Math.sqrt(missedSum * missedSum - 4 * missedProduct)) / 2;
        Double secondMissedNum = (missedSum - Math.sqrt(missedSum * missedSum - 4 * missedProduct)) / 2;
        return new int[]{firstMissedNum.intValue(), secondMissedNum.intValue()};
    }

и простой генератор массивов для тестов

  public static Map.Entry<int[], int[]> generateArray(int maxN, int missedNumbersCount) {
        int[] initialArr = new int[maxN];
        for (int i = 0; i < maxN; i++) {
            initialArr[i] = i + 1;
        }
        shuffleArray(initialArr);
        int[] skippedNumbers = Arrays.copyOfRange(initialArr, maxN - missedNumbersCount, maxN);
        int[] arrayWithoutSkippedNumbers = Arrays.copyOf(initialArr, maxN - missedNumbersCount);
        return new AbstractMap.SimpleEntry<>(arrayWithoutSkippedNumbers, skippedNumbers);

    }

    private static void shuffleArray(int[] ar) {
        Random rnd = ThreadLocalRandom.current();
        for (int i = ar.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            // Simple swap
            int a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
        }
    }

Ответ 12

#include <iostream>
using namespace std;
int main() {
    int arr[]={3,1,2,5,7,8};
    int n=6;
    for(int i=0;i<n;i++){
        if(arr[i]>0 && arr[i]<=n){
            int temp=arr[i]-1;
            if(arr[i]!=arr[temp]){
            swap(arr[i],arr[temp]);
            i--;
            }
        }
    }
    for(int i=0;i<n;i++){
        if(arr[i]!=i+1)
        cout<<i+1<<endl;
    }
    // your code goes here
    return 0;
}

Мы можем использовать тот же массив, что и ведро. Мы проходим его один раз и продолжаем заменять элемент на правильный индекс. Если значение меньше 1 или больше длины массива, мы оставляем его как есть. Начальный массив- 3 1 2 5 7 8 подкачки (3,5) 5 1 2 3 7 8 подкачки (5,8) 8 1 2 3 7 5 После этого мы снова пересекаем массив. Элементы, которые не находятся в правильном положении, отсутствуют, поэтому мы печатаем индекс. Сложность времени-O (n)

Ответ 13

Используя набор битов, мы можем найти n пропущенных элементов, но список должен начинаться с 1. В приведенном ниже методе числа - это целочисленный массив, а число - это общее количество элементов, включая пропущенные числа. count = 9 означает, что список начинается с 1-9 (с 9 целыми числами), 5 целых даны в массиве и 4 отсутствуют

public class FindMissingNumberInArray {

    static void printMissingNumber(int[] numbers, int count) {
        int missingCount = count - numbers.length;
        BitSet bitSet = new BitSet(count);
        for (int number : numbers) {
            bitSet.set(number-1);
        }

        int lastMissingIndex = 0;
        for(int i = 0;i<missingCount;i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }

    }
    public static void main(String[] args) {
        int[] array = {3,4,5,7,8};
        printMissingNumber(array, 9);
        }
}

**Output:**
1
2
6
9

Ответ 14

вам просто нужно XOR массив, заданный с полным массивом, и выяснить, нет ли нулевых элементов....