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

matriz 3x3 java

Question

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.

Answer 1

5050 - (suma 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);

Answer 2

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

Answer 3

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

}

Answer 4

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.

Answer 5

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

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

Answer 6

Aquí la complejidad del tiempo de ejecución del programa 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);

  }
 }

Answer 7

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<<i & 1); i++);
    return i;
}

Answer 8

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.

Answer 9

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

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

Answer 10

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
}

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

Este no es un problema de búsqueda. El empleador se pregunta si tiene una comprensión de una suma 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 suma 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

Answer 15

Este programa encuentra los números que faltan

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

}
?>

Answer 16

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;

Answer 17

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

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.

Answer 18

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

Answer 19

Podemos usar la operación XOR que es más segura que la suma porque en los lenguajes de programació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;

Answer 20

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 suma de todos los números naturales de 1 a n (en este caso n es 100). Ahora que sabemos la suma que debería ser de 1 a 100, solo restamos restar la suma 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 suma de números perdidos, con la misma lógica que antes. Segundo, encontrar el número más pequeño entre la suma 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 suma 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 repositorio de Github para preguntas y respuestas de la Entrevista .

Answer 21

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.

Answer 22

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

Answer 23

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.

Answer 24

Use la fórmula de suma,

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/

Answer 25

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

Reste la suma 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 suma.

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

Answer 26

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

Answer 27

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

Answer 28

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

Answer 29

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;

}
}

Answer 30

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