La forma más rápida de encontrar el número que falta en una matriz de números

Tengo una matriz de números del 1 al 100 (ambos inclusive). El tamaño de la matriz es 100. Los números se agregan aleatoriamente a la matriz, pero hay una ranura aleatoria vacía en la matriz. ¿Cuál es la forma más rápida de encontrar esa ranura, así como el número que debe colocarse en la ranura? Una solución Java es preferible.

Puedes hacer esto en O (n). Itera a través de la matriz y calcule la sum de todos los números. Ahora, la sum de los números naturales de 1 a N se puede express como Nx(N+1)/2 . En tu caso N = 100.

Reste la sum de la matriz de Nx(N+1)/2 , donde N = 100.

Ese es el número que falta. La ranura vacía se puede detectar durante la iteración en la que se calcula la sum.

 // will be the sum of the numbers in the array. int sum = 0; int idx = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] == 0) { idx = i; } else { sum += arr[i]; } } // the total sum of numbers between 1 and arr.length. int total = (arr.length + 1) * arr.length / 2; System.out.println("missing number is: " + (total - sum) + " at index " + idx); 

Podemos usar la operación XOR que es más segura que la sum porque en los lenguajes de progtwigción, si la entrada dada es grande, puede desbordarse y dar una respuesta incorrecta.

Antes de ir a la solución, sepa que A xor A = 0 . Entonces, si hacemos XOR dos números idénticos, el valor es 0.

Ahora, XORing [1..n] con los elementos presentes en la matriz cancela los números idénticos. Entonces, al final obtendremos el número que falta.

 // 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); 

Esta fue una pregunta de la entrevista de Amazon y fue respondida originalmente aquí: Tenemos números del 1 al 52 que se ponen en un conjunto de 51 números, ¿cuál es la mejor manera de averiguar qué número falta?

Fue respondida, como abajo:

 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. 

También se escribió en el blog aquí: Software Job: pregunta de la entrevista

Aquí hay un progtwig simple para encontrar los números que faltan en una matriz de enteros

 ArrayList arr = new ArrayList(); int a[] = { 1,3,4,5,6,7,10 }; int j = a[0]; for (int i=0;i 

5050 – (sum de todos los valores en la matriz) = número faltante

 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); 

En un escenario similar, donde la matriz ya está ordenada , no incluye duplicados y solo falta un número, es posible encontrar este número faltante en tiempo de registro (n) , utilizando la búsqueda binaria.

 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 } 

Esto es c #, pero debería ser muy parecido a lo que necesita:

 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; 

Bueno, usa un filtro de floración.

 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< 

La solución que no incluye adiciones repetitivas o quizás la fórmula n (n + 1) / 2 no le llega en un momento de entrevista, por ejemplo.

Debe usar una matriz de 4 entradas (32 bits) o 2 entradas (64 bits). Inicialice el último int con (-1 y ~ (1 << 31)) >> 3. (los bits que están por encima de 100 están establecidos en 1) O puede establecer los bits por encima de 100 utilizando un ciclo for.

  1. Examine la matriz de números y establezca 1 para la posición del bit correspondiente al número (por ejemplo, 71 se establecerá en la 3ª entrada en el 7º bit de izquierda a derecha)
  2. Ir a través de la matriz de 4 entradas (versión de 32 bits) o 2 entradas (versión de 64 bits)
 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) }
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) } 

Ejemplo: (versión de 32 bits) digamos que el número que falta es 58. Eso significa que el 26º bit (de izquierda a derecha) del segundo entero se establece en 0.

El primer int es -1 (todos los bits están configurados), así que seguimos adelante con el segundo y agregamos “no” al número 32. El segundo int es diferente de -1 (un bit no está establecido) así que, al aplicar el operador NOT (~) al número que obtenemos 64. Los números posibles son 2 a la potencia x y podemos calcular x usando log on base 2; en este caso obtenemos log2 (64) = 6 => 32 + 32 – 6 = 58.

Espero que esto ayude.

Este no es un problema de búsqueda. El empleador se pregunta si tiene una comprensión de una sum de comprobación. Es posible que necesite un binario o bucle o lo que sea si estuviera buscando múltiples enteros únicos, pero la pregunta estipula “un espacio vacío al azar”. En este caso, podemos usar la sum de la secuencia. La condición: “Los números se agregan aleatoriamente a la matriz” no tiene sentido sin más detalles. La pregunta no supone que la matriz debe comenzar con el número entero 1 y tolerar con el entero de inicio de desplazamiento.

 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); 

Tiempo de éxito: 0.18 de memoria: 320576 de señal: 0

Encontré esta hermosa solución aquí:

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); } } 

======== Solución más simple para la matriz ordenada ===========

 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; } 

Encontrar el número que falta de una serie de números. IMP apunta a recordar.

  1. la matriz debe ser ordenada …
  2. la función no funciona en múltiples errores.
  3. la secuencia debe ser un 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>> 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; } 

Creo que la solución más fácil y posiblemente la más eficiente sería recorrer todas las entradas y utilizar un conjunto de bits para recordar qué números se establecen y luego probar para 0 bit. La entrada con el bit 0 es el número que falta.

Este progtwig encuentra los números que faltan

  

Una cosa que podrías hacer es ordenar los números usando clasificación rápida, por ejemplo. A continuación, utilice un ciclo for para recorrer el conjunto ordenado de 1 a 100. En cada iteración, compara el número en el conjunto con su incremento de ciclo, si encuentra que el incremento del índice no es el mismo que el valor del conjunto, ha encontrado su número que falta, así como el índice que falta.

A continuación se muestra la solución para encontrar todos los números que faltan de una matriz determinada:

 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 arrayList = new ArrayList(); 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); } } 

Digamos que tiene n como 8, y nuestros números van de 0-8 para este ejemplo, podemos representar la representación binaria de los 9 números de la siguiente manera 0000 0001 0010 0011 0100 0101 0110 0111 1000

en la secuencia anterior no faltan números y en cada columna coincide el número de ceros y unos, sin embargo, tan pronto como elimines 1 valor, digamos 3 obtenemos un saldo en el número de 0 y 1 a través de las columnas. Si el número de 0 en una columna es <= el número de 1, nuestro número faltante tendrá un 0 en esta posición de bit, de lo contrario, si el número de 0 es> el número de 1 en esta posición de bit, entonces esta posición de bit será un 1 . Probamos los bits de izquierda a derecha y en cada iteración tiramos la mitad de la matriz para la prueba del siguiente bit, ya sea los valores impares de la matriz o los valores uniformes de la matriz se descartan en cada iteración dependiendo de qué bit estamos deficientes. en.

La siguiente solución está en C ++

 int getMissingNumber(vector* input, int bitPos, const int startRange) { vector zeros; vector 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; isize(); 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; } 

En cada iteración reducimos nuestro espacio de entrada en 2, es decir, N, N / 2, N / 4 ... = O (log N), con espacio 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 

Solución con PHP $ n = 100 ;

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

y array_search($missing_number) dará el índice del número que falta

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

Aquí la complejidad del tiempo de ejecución del progtwig es O (logn) y la complejidad del espacio 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; } } 

Recientemente tuve una pregunta similar (no exactamente la misma) en una entrevista de trabajo y también escuché de un amigo que se le hizo exactamente la misma pregunta en una entrevista. Así que aquí hay una respuesta a la pregunta OP y algunas otras variaciones que pueden ser potencialmente formuladas. El ejemplo de las respuestas se da en Java porque se afirma que:

Una solución Java es preferible.

Solución 1:

Matriz de números del 1 al 100 (ambos inclusive) … Los números se agregan aleatoriamente a la matriz, pero hay una ranura aleatoria vacía en la matriz

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

Explicación: esta solución (como muchas otras soluciones publicadas aquí) se basa en la fórmula del Triangular number , que nos da la sum de todos los números naturales de 1 a n (en este caso n es 100). Ahora que sabemos la sum que debería ser de 1 a 100, solo restamos restar la sum real de los números existentes en la matriz dada.

Solución 2:

Matriz de números del 1 al n (lo que significa que el número máximo es desconocido)

 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; } 

Explicación: En esta solución, dado que no se proporciona el número máximo, tenemos que encontrarlo. Después de encontrar el número máximo, la lógica es la misma.

Solución 3:

Matriz de números del 1 al n (el número máximo es desconocido), hay dos ranuras vacías al azar en el conjunto

 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; } 

Explicación: En esta solución, el número máximo no se proporciona (como en el caso anterior), pero también puede faltar dos números y no uno. Así que al principio encontramos la sum de números perdidos, con la misma lógica que antes. Segundo, encontrar el número más pequeño entre la sum faltante y el último número (posiblemente) que falta, para reducir la búsqueda innecesaria. En tercer lugar, dado que Java s Array (no una colección) no tiene métodos como indexOf o contains , agregué un pequeño método reutilizable para esa lógica. En cuarto lugar cuando se encuentra el primer número que falta, el segundo es el resta de la sum faltante. Si solo falta un número, entonces el segundo número en el conjunto será cero.

Nota

Si desea ejemplos en otros idiomas u otras variaciones interesantes de esta pregunta , puede consultar mi repository de Github para preguntas y respuestas de la Entrevista .

Use la fórmula de sum,

 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); } } 

Referencia 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** 

Si la matriz se llena aleatoriamente, entonces en el mejor de los casos puede hacer una búsqueda lineal en O (n) complejidad. Sin embargo, podríamos haber mejorado la complejidad de O (log n) mediante el método de dividir y conquistar, similar al método de ordenación rápida, tal como lo señala el giri dado que los números estaban en orden ascendente / descendente.

Ahora estoy demasiado afilado con las notaciones de Big O, pero no podría hacer algo como (en Java)

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

donde números es la matriz con sus números del 1-100. A partir de mi lectura de la pregunta, no decía cuándo escribir el número que faltaba.

Alternativamente, si PODRÍA arrojar el valor de i + 1 en otra matriz e imprimirlo después de la iteración.

Por supuesto, podría no cumplir con las reglas de tiempo y espacio. Como ya he dicho. Tengo que repasar fuertemente en Big O.

Otra pregunta sobre la tarea. Una búsqueda secuencial es lo mejor que puedes hacer. En cuanto a una solución de Java, considere que es un ejercicio para el lector. :PAG