Быстрый способ найти недостающее число в массиве чисел

мы можем использовать операцию XOR, которая безопаснее, чем суммирование, потому что в языках программирования, если данный вход большой, он может переполниться и может дать неправильный ответ.

прежде чем перейти к решению, знать, что A xor A = 0. Поэтому, если мы XOR два одинаковых числа, значение равно 0.

Теперь, XORing [1..n] с элементами, присутствующими в массиве, отменяет одинаковые числа. Так что в конце мы получим недостающее число.

// Assuming that the array contains 99 distinct integers between 1..99
// and empty slot value is zero
int XOR = 0;
for(int i=0; i<100; i++) {
    if (ARRAY[i] != 0)
        XOR ^= ARRAY[i];
    XOR ^= (i + 1);
}
return XOR;

long n = 100;
int a[] = new int[n];

//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0

long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;

for (long i = 1; i <= n; i++)
{
    xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);

Это был вопрос интервью Amazon и первоначально был дан ответ здесь:У нас есть числа от 1 до 52, которые помещаются в массив чисел 51, каков наилучший способ узнать, какое число отсутствует?

был дан ответ, как показано ниже:

1) Calculate the sum of all numbers stored in the array of size 51. 
2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2.

это также было опубликовано здесь:Программное Обеспечение Работа-Интервью Вопрос

вот простая программа для поиска недостающих чисел в целочисленном массиве

ArrayList<Integer> arr = new ArrayList<Integer>();
int a[] = { 1,3,4,5,6,7,10 };
int j = a[0];
for (int i=0;i<a.length;i++)
{
    if (j==a[i])
    {
        j++;
        continue;
    }
    else
    {
        arr.add(j);
        i--;
    j++;
    }
}
System.out.println("missing numbers are ");
for(int r : arr)
{
    System.out.println(" " + r);
}

5050 - (сумма всех значений в массиве) = недостающее количество

int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++) {
  if (arr[i] == 0) idx = i; else sum += arr[i];
}
System.out.println("missing number is: " + (5050 - sum) + " at index " + idx);

по аналогичному сценарию,если массив уже отсортирован, он не включает дубликаты и только один номер отсутствует, можно найти это недостающее число в log (n) time, используя бинарный поиск.

public static int getMissingInt(int[] intArray, int left, int right) {
    if (right == left + 1) return intArray[right] - 1;
    int pivot = left + (right - left) / 2;
    if (intArray[pivot] == intArray[left] + (intArray[right] - intArray[left]) / 2 - (right - left) % 2)
        return getMissingInt(intArray, pivot, right);
    else 
        return getMissingInt(intArray, left, pivot);
}

public static void main(String args[]) {
    int[] array = new int[]{3, 4, 5, 6, 7, 8, 10};
    int missingInt = getMissingInt(array, 0, array.length-1);
    System.out.println(missingInt); //it prints 9
}

Это C#, но это должно быть довольно близко к тому, что вам потребуется:

int sumNumbers = 0;
int emptySlotIndex = -1;

for (int i = 0; i < arr.length; i++)
{
  if (arr[i] == 0)
    emptySlotIndex = i;
  sumNumbers += arr[i];
}

int missingNumber = 5050 - sumNumbers;

Ну, используйте фильтр цветения.

int findmissing(int arr[], int n)
{
    long bloom=0;
    int i;
    for(i=0; i<;n; i++)bloom+=1>>arr[i];
    for(i=1; i<=n, (bloom<<i & 1); i++);
    return i;
}

решение, которое не включает повторяющиеся дополнения или, возможно, формула n(n+1)/2 не попадает к вам во время интервью, например.

вы должны использовать массив из 4 ints (32 бита) или 2 ints (64 бита). Инициализируйте последний int с помощью (-1 & ~(1 > 3. (биты, которые выше 100, установлены в 1) или вы можете установить биты выше 100, используя цикл for.

1. пройдите через массив чисел и установите 1 для позиции бита, соответствующей номеру (например, 71 будет установлен на 3-й int на 7-й бит слева направо)
2. пройдите через массив из 4 ints(32-битная версия) или 2 ints (64-битная версия)

    public int MissingNumber(int a[])
    {   
        int bits = sizeof(int) * 8;
        int i = 0;
        int no = 0;
        while(a[i] == -1)//this means a[i]'s bits are all set to 1, the numbers is not inside this 32 numbers section
        {
            no += bits;
            i++;
        }
        return no + bits - Math.Log(~a[i], 2);//apply NOT (~) operator to a[i] to invert all bits, and get a number with only one bit set (2 at the power of something)
    }

пример: (32-разрядная версия) допустим, что отсутствует число 58. Это означает, что 26-й бит (слева направо) второго целого числа имеет значение 0.

первый int равен -1 (все биты установлены), поэтому мы идем вперед для второго и добавляем к "нет" число 32. Второй int отличается от -1 (бит не установлен) таким образом, применяя оператор NOT ( ~ ) к числу, которое мы получаем 64. Возможные числа равны 2 в степени x, и мы можем вычислить x с помощью log on base 2; в этом случае мы получаем log2(64) = 6 => 32 + 32 - 6 = 58.

надеюсь, что это помогает.

Это не проблема поиска. Работодатель задается вопросом, если у вас есть понимание контрольной суммы. Вам может понадобиться двоичный или для цикла или что-то еще, если вы ищете несколько уникальных целых чисел, но вопрос предусматривает "один случайный пустой слот."В этом случае мы можем использовать сумму потока. Условие:" числа случайным образом добавляются в массив " бессмысленно без более подробной информации. Вопрос не предполагает, что массив должен начинаться с целого числа 1 и поэтому допускает начало смещения целое число.

int[] test = {2,3,4,5,6,7,8,9,10,  12,13,14 };

/*get the missing integer*/

int max = test[test.length - 1];
int min = test[0];
int sum = Arrays.stream(test).sum();
int actual = (((max*(max+1))/2)-min+1);
//Find:

//the missing value
System.out.println(actual - sum);
//the slot
System.out.println(actual - sum - min);

время успеха: 0.18 память: 320576 сигнал: 0

Я нашел это прекрасное решение здесь:

http://javaconceptoftheday.com/java-puzzle-interview-program-find-missing-number-in-an-array/

public class MissingNumberInArray
{
    //Method to calculate sum of 'n' numbers

    static int sumOfNnumbers(int n)
    {
        int sum = (n * (n+1))/ 2;

        return sum;
    }

    //Method to calculate sum of all elements of array

    static int sumOfElements(int[] array)
    {
        int sum = 0;

        for (int i = 0; i < array.length; i++)
        {
            sum = sum + array[i];
        }

        return sum;
    }

    public static void main(String[] args)
    {
        int n = 8;

        int[] a = {1, 4, 5, 3, 7, 8, 6};

        //Step 1

        int sumOfNnumbers = sumOfNnumbers(n);

        //Step 2

        int sumOfElements = sumOfElements(a);

        //Step 3

        int missingNumber = sumOfNnumbers - sumOfElements;

        System.out.println("Missing Number is = "+missingNumber);
    }
}

поиск недостающего числа из ряда чисел. ИМП указывает, чтобы запомнить.

1. массив должен быть отсортирован..
2. функция не работает на нескольких пропусков.

3. последовательность должна быть AP.

       public int execute2(int[] array) {
       int diff = Math.min(array[1]-array[0], array[2]-array[1]);
       int min = 0, max = arr.length-1;
       boolean missingNum = true;
       while(min<max) {
           int mid = (min + max) >>> 1;
           int leftDiff = array[mid] - array[min];
           if(leftDiff > diff * (mid - min)) {
               if(mid-min == 1)
                   return (array[mid] + array[min])/2;
               max = mid;
               missingNum = false;
               continue;
           }
           int rightDiff = array[max] - array[mid];
           if(rightDiff > diff * (max - mid)) {
               if(max-mid == 1)
                   return (array[max] + array[mid])/2;
               min = mid;
               missingNum = false;
               continue;
           }
           if(missingNum)
               break;
       }
       return -1;
   }
   

Я думаю, что самый простой и, возможно, наиболее эффективным решением было бы перебрать все записи и использовать bitset, чтобы вспомнить, какие числа, и затем проверить на 0 бит. Запись с 0 бит-это пропущенное число.

эта программа находит недостающие цифры

<?php
$arr_num=array("1","2","3","5","6");
$n=count($arr_num);
for($i=1;$i<=$n;$i++)
{       
      if(!in_array($i,$arr_num))
      {
      array_push($arr_num,$i);print_r($arr_num);exit;
      }

}
?>

одна вещь, которую вы могли бы сделать, это сортировать числа, используя быструю сортировку, например. Затем используйте цикл for для итерации по отсортированному массиву от 1 до 100. На каждой итерации вы сравниваете число в массиве с приращением цикла for, если вы обнаружите, что приращение индекса не совпадает со значением массива, вы нашли свой отсутствующий номер, а также отсутствующий индекс.

Ниже приводится решение для поиска всех недостающих чисел из данного массива:

public class FindMissingNumbers {

/**
 * The function prints all the missing numbers from "n" consecutive numbers.
 * The number of missing numbers is not given and all the numbers in the
 * given array are assumed to be unique.
 * 
 * A similar approach can be used to find all no-unique/ unique numbers from
 * the given array
 * 
 * @param n
 *            total count of numbers in the sequence
 * @param numbers
 *            is an unsorted array of all the numbers from 1 - n with some
 *            numbers missing.
 * 
 */
public static void findMissingNumbers(int n, int[] numbers) {

    if (n < 1) {
        return;
    }

    byte[] bytes = new byte[n / 8];
    int countOfMissingNumbers = n - numbers.length;

    if (countOfMissingNumbers == 0) {
        return;
    }

    for (int currentNumber : numbers) {

        int byteIndex = (currentNumber - 1) / 8;
        int bit = (currentNumber - byteIndex * 8) - 1;
        // Update the "bit" in bytes[byteIndex]
        int mask = 1 << bit;
        bytes[byteIndex] |= mask;
    }
    for (int index = 0; index < bytes.length - 2; index++) {
        if (bytes[index] != -128) {
            for (int i = 0; i < 8; i++) {
                if ((bytes[index] >> i & 1) == 0) {
                    System.out.println("Missing number: " + ((index * 8) + i + 1));
                }
            }
        }
    }
    // Last byte
    int loopTill = n % 8 == 0 ? 8 : n % 8;
    for (int index = 0; index < loopTill; index++) {
        if ((bytes[bytes.length - 1] >> index & 1) == 0) {
            System.out.println("Missing number: " + (((bytes.length - 1) * 8) + index + 1));
        }
    }

}

public static void main(String[] args) {

    List<Integer> arrayList = new ArrayList<Integer>();
    int n = 128;
    int m = 5;
    for (int i = 1; i <= n; i++) {
        arrayList.add(i);
    }
    Collections.shuffle(arrayList);
    for (int i = 1; i <= 5; i++) {
        System.out.println("Removing:" + arrayList.remove(i));
    }
    int[] array = new int[n - m];
    for (int i = 0; i < (n - m); i++) {
        array[i] = arrayList.get(i);
    }
    System.out.println("Array is: " + Arrays.toString(array));

    findMissingNumbers(n, array);
}

}

Допустим, у вас есть n как 8, и наши числа варьируются от 0-8 для этого примера мы можем представить двоичное представление всех 9 чисел следующим образом Ноль ноль ноль ноль Ноль ноль ноль один Ноль ноль десять Ноль ноль одиннадцать Ноль сто Ноль сто один Ноль сто десять Ноль сто одиннадцать 1000

в приведенной выше последовательности нет отсутствующих чисел и в каждом столбце количество нулей и единиц совпадают, однако, как только вы удалите значение 1, скажем, 3, мы получим баланс в количестве 0 и 1 по столбцам. Если число 0 в столбце число 1 в этой битовой позиции, то эта битовая позиция будет 1. Мы тестируем биты слева направо и на каждой итерации выбрасываем половину массива для тестирования следующего бита, либо нечетные значения массива, либо четные значения массива выбрасываются на каждой итерации в зависимости от того, какой бит нам не хватает.

ниже решение находится в C++

int getMissingNumber(vector<int>* input, int bitPos, const int startRange)
{
    vector<int> zeros;
    vector<int> ones;
    int missingNumber=0;

    //base case, assume empty array indicating start value of range is missing
    if(input->size() == 0)
        return startRange;

    //if the bit position being tested is 0 add to the zero's vector
    //otherwise to the ones vector
    for(unsigned int i = 0; i<input->size(); i++)
    {
        int value = input->at(i);
        if(getBit(value, bitPos) == 0)
            zeros.push_back(value);
        else
            ones.push_back(value);
    }

    //throw away either the odd or even numbers and test
    //the next bit position, build the missing number
    //from right to left
    if(zeros.size() <= ones.size())
    {
        //missing number is even
        missingNumber = getMissingNumber(&zeros, bitPos+1, startRange);
        missingNumber = (missingNumber << 1) | 0;
    }
    else
    {
        //missing number is odd
        missingNumber = getMissingNumber(&ones, bitPos+1, startRange);
        missingNumber = (missingNumber << 1) | 1;
    }

    return missingNumber;
}

на каждой итерации мы снижаем нашу входного пространства на 2, я.е н, н/2,Н/4 ... = O (log N), с пробелом O(N)

//Test cases 
[1] when missing number is range start
[2] when missing number is range end
[3] when missing number is odd
[4] when missing number is even

решение с PHP $n = 100;

$n*($n+1)/2 - array_sum($array) = $missing_number

и array_search($missing_number) даст индекс недостающего числа

function solution($A) {
    // code in PHP5.5
    $n=count($A);
    for($i=1;$i<=$n;$i++) {
       if(!in_array($i,$A)) {
              return (int)$i;
       }
    }
}

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

public int getMissingNumber(int[] sortedArray)
        {
            int missingNumber = 0;
            int missingNumberIndex=0;
            for (int i = 0; i < sortedArray.length; i++)
            {
                if (sortedArray[i] == 0)
                {
                    missingNumber = (sortedArray[i + 1]) - 1;
                    missingNumberIndex=i;
                    System.out.println("missingNumberIndex: "+missingNumberIndex);
                    break;
                }
            }
            return missingNumber;
        }

здесь программа принимает сложность времени O (logn) и сложность пространства O(logn)

public class helper1 {

public static void main(String[] args) {


    int a[] = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12};


    int k = missing(a, 0, a.length);
    System.out.println(k);
}

public static int missing(int[] a, int f, int l) {


    int mid = (l + f) / 2;

    //if first index reached last then no element found 
    if (a.length - 1 == f) {
        System.out.println("missing not find ");
        return 0;
    }

    //if mid with first found 
    if (mid == f) {
        System.out.println(a[mid] + 1);
        return a[mid] + 1;
    }

    if ((mid + 1) == a[mid])
        return missing(a, mid, l);
    else
        return missing(a, f, mid);

  }
 }

public class MissingNumber {

public static void main(String[] args) {
     int array[] = {1,2,3,4,6};
     int x1 = getMissingNumber(array,6);
    System.out.println("The Missing number is: "+x1);


}
private static int getMissingNumber(int[] array, int i) {

    int acctualnumber =0;
    int expectednumber = (i*(i+1)/2);

    for (int j : array) {
        acctualnumber = acctualnumber+j;

    }
    System.out.println(acctualnumber);
    System.out.println(expectednumber);
    return expectednumber-acctualnumber;

}
}

недавно у меня был подобный (не точно такой же) вопрос на собеседовании, а также я слышал от друга, который был задан точно такой же вопрос в интервью. Итак, вот ответ на вопрос OP и еще несколько вариантов, которые могут быть потенциально заданы. Пример ответов приведен в Java, потому что, он заявил, что:

решение Java предпочтительнее.

решение 1:

массив чисел от 1 до 100 (включительно) ... Числа случайным образом добавляются в массив, но есть один случайный пустой слот в массиве

public static int findMissing1(int [] arr){
    int sum = 0;
    for(int n : arr){
        sum += n;
    }
    return (100*(100+1)/2) - sum;
}

объяснение: Это решение (как и многие другие решения, размещенные здесь) основано на Формуле Triangular number, что дает нам сумму всех натуральных чисел от 1 до n (в данном случае n на 100). Теперь, когда мы знаем сумму, которая должна быть от 1 до 100 - нам просто нужно вычесть фактическую сумму существующих чисел в данном массиве.

решение 2:

массив чисел от 1 до n (это означает, что максимальное число неизвестно)

public static int findMissing2(int [] arr){
    int sum = 0, max = 0;
    for(int n : arr){
        sum += n;
        if(n > max) max = n;
    }
    return (max*(max+1)/2) - sum;
}

объяснение: В этом решении, поскольку максимальное число не задано-нам нужно его найти. После нахождения максимального числа-логика та же.

решение 3:

массив чисел от 1 до n (максимальное число неизвестно), есть два случайных пустых слота в массиве

public static int [] findMissing3(int [] arr){
    int sum = 0, max = 0, misSum;
    int [] misNums = {};//empty by default
    for(int n : arr){
        sum += n;
        if(n > max) max = n;
    }
    misSum = (max*(max+1)/2) - sum;//Sum of two missing numbers
    for(int n = Math.min(misSum, max-1); n > 1; n--){
        if(!contains(n, arr))misNums = new int[]{n, misSum-n};

    }
    return misNums;
}
private static boolean contains(int num, int [] arr){
    for(int n : arr){
        if(n == num)return true;
    }
    return false;
}

объяснение: В этом решении максимальное число не задано (как и в предыдущем), но также может отсутствовать два числа, а не одно. Поэтому сначала мы находим сумму недостающих чисел-с той же логикой, что и раньше. Во-вторых, найти меньшее число между недостающей суммой и последней (возможно) недостающее число-для уменьшения ненужного поиска. В-третьих, начиная с Javaмассив s (не коллекция) не имеет методов как indexOf или contains, я добавил небольшой многоразовый метод для этой логики. В-четвертых, когда первое отсутствующее число найдено, второе-это вычесть из отсутствующей суммы. Если отсутствует только одно число, то второе число в массиве будет равно нулю.

Примечание

если вы хотите примеры в другие языки или другой интересные вариации этого вопроса, вы можете проверить мои Github хранилище интервью вопросы и ответы.

использовать формулу суммы,

class Main {
// Function to ind missing number
     static int getMissingNo (int a[], int n) {
          int i, total;
          total  = (n+1)*(n+2)/2;   
          for ( i = 0; i< n; i++)
              total -= a[i];
          return total;
     }

    /* program to test above function */
    public static void main(String args[]) {

        int a[] = {1,2,4,5,6};
        int miss = getMissingNo(a,5);
        System.out.println(miss);   
   }
}

Ссылка http://www.geeksforgeeks.org/find-the-missing-number/

simple solution with test data :

class A{

  public static void main(String[] args){
    int[] array = new int[200];
    for(int i=0;i<100;i++){
      if(i != 51){
        array[i] = i;  
      }
    }

    for(int i=100;i<200;i++){
      array[i] = i;  
    }

    int temp = 0;
    for(int i=0;i<200;i++){
      temp ^= array[i];
    }

    System.out.println(temp);
  }
} 

    //Array is shorted and if writing in C/C++ think of XOR implementations in java as follows.
                    int num=-1;
    for (int i=1; i<=100; i++){
        num =2*i;
        if(arr[num]==0){
         System.out.println("index: "+i+" Array position: "+ num);      
         break;
        }
        else if(arr[num-1]==0){
         System.out.println("index: "+i+ " Array position: "+ (num-1)); 
         break;             
        }           
    }// use Rabbit and tortoise race, move the dangling index faster, 
     //learnt from Alogithimica, Ameerpet, hyderbad**

Если массив заполнен случайным образом, то в лучшем случае вы можете выполнить линейный поиск в сложности O(n). Однако мы могли бы улучшить сложность до O (log n) путем разделения и завоевания подхода, аналогичного быстрой сортировке, как указано гири, учитывая, что числа были в порядке возрастания/убывания.

теперь я теперь слишком острый с большими нотациями O, но не могли бы вы также сделать что-то вроде (в Java)

for (int i = 0; i < numbers.length; i++) {
    if(numbers[i] != i+1){
        System.out.println(i+1);
    }
}

где numbers-это массив с вашими номерами от 1-100. Из моего чтения вопроса он не сказал, когда выписать недостающее число.

альтернативно, если вы можете бросить значение i+1 в другой массив и распечатать его после итерации.

конечно, он может не соблюдать правила времени и пространства. Как я уже сказал. Мне пришлось сильно освежить большой О.

еще один вопрос домашнего задания. Последовательный поиск-это лучшее, что вы можете сделать. Что касается решения Java, считайте, что это упражнение для читателя. : P