wake-up-neo.com

Der schnellste Weg, fehlende Zahlen in einem Zahlenfeld zu finden

Ich habe ein Zahlenfeld von 1 bis 100 (beide inklusive). Die Größe des Arrays ist 100. Die Zahlen werden zufällig dem Array hinzugefügt, aber es gibt einen zufälligen leeren Platz im Array. Was ist der schnellste Weg, um diesen Steckplatz zu finden, sowie die Nummer, die in den Steckplatz gesetzt werden sollte? Eine Java-Lösung ist vorzuziehen.

67
Thunderhashy

Sie können dies in O (n) tun. Durchlaufen Sie das Array und berechnen Sie die Summe aller Zahlen. Nun kann die Summe der natürlichen Zahlen von 1 bis N als Nx(N+1)/2 ausgedrückt werden. In Ihrem Fall ist N = 100.

Subtrahiere die Summe des Arrays von Nx(N+1)/2, wobei N = 100 ist.

Das ist die fehlende Nummer. Der leere Slot kann während der Iteration ermittelt werden, in der die Summe berechnet wird.

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

Wir können die XOR Operation verwenden, die sicherer ist als die Summation, da in Programmiersprachen, wenn die Eingabe groß ist, sie überlaufen und eine falsche Antwort geben kann.

Bevor Sie zur Lösung gehen, sollten Sie wissen, dass A xor A = 0. Wenn wir also XOR zwei identische Zahlen verwenden, ist der Wert 0. 

Wenn Sie nun XORing [1..n] mit den im Array vorhandenen Elementen verwenden, werden die identischen Zahlen gelöscht. Am Ende bekommen wir die fehlende Nummer.

// 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;
24
Dungeon Hunter

Das gegebene Array sei A mit der Länge N. Nehmen wir an, dass in dem gegebenen Array der einzelne leere Slot mit 0 gefüllt ist.

Wir können die Lösung für dieses Problem mit vielen Methoden finden, einschließlich des in Counting sort verwendeten Algorithmus. Im Hinblick auf eine effiziente Nutzung von Zeit und Raum haben wir jedoch zwei Algorithmen. Man verwendet hauptsächlich Summation, Subtraktion und Multiplikation. Ein anderer verwendet XOR. Mathematisch funktionieren beide Methoden gut. Aber programmatisch müssen wir alle Algorithmen mit Hauptmaßen wie bewerten

  • Einschränkungen (wie Eingabewerte sind groß (A[1...N]) und/oder Anzahl der Eingabewerte ist groß (N))
  • Anzahl der beteiligten Zustandsüberprüfungen
  • Anzahl und Art der beteiligten mathematischen Operationen

usw. Dies liegt an den zeitlichen und/oder hardwaretechnischen Einschränkungen (Beschränkung der Hardwareressourcen) und/oder der Software (Beschränkung des Betriebssystems, Beschränkung der Programmiersprache usw.) .

Algorithmus 1:

In Algorithmus 1 haben wir 3 Implementierungen.

  1. Berechnen Sie die Gesamtsumme aller Zahlen (einschließlich der unbekannten fehlenden Zahl) mithilfe der mathematischen Formel (1+2+3+...+N=(N(N+1))/2). Hier N=100. Berechnen Sie die Gesamtsumme aller angegebenen Zahlen. Subtrahieren Sie das zweite Ergebnis vom ersten Ergebnis, um die fehlende Zahl zu erhalten.

    Missing Number = (N(N+1))/2) - (A[1]+A[2]+...+A[100])

  2. Berechnen Sie die Gesamtsumme aller Zahlen (einschließlich der unbekannten fehlenden Zahl) mithilfe der mathematischen Formel (1+2+3+...+N=(N(N+1))/2). Hier N=100. Subtrahieren Sie von diesem Ergebnis jede gegebene Zahl, um die fehlende Zahl zu erhalten.

    Missing Number = (N(N+1))/2)-A[1]-A[2]-...-A[100]

    (Note:Auch wenn die Formel der zweiten Implementierung von der ersten abgeleitet wird, sind beide aus mathematischer Sicht gleich. Aus programmtechnischer Sicht sind beide unterschiedlich, da die erste Formel für Bitüberlauf anfälliger ist als die zweite (wenn die angegebenen Zahlen) Obwohl die Addition schneller ist als die Subtraktion, verringert die zweite Implementierung die Wahrscheinlichkeit eines Bitüberlaufs, der durch Addition großer Werte verursacht wird (dies ist nicht vollständig beseitigt, da die Wahrscheinlichkeit immer noch sehr gering ist, da (N+1) in der Formel vorhanden ist Beide sind jedoch gleichermaßen anfällig für Bitüberlauf durch Multiplikation. Die Einschränkung besteht darin, dass beide Implementierungen nur dann ein korrektes Ergebnis liefern, wenn N(N+1)<=MAXIMUM_NUMBER_VALUE. Bei der ersten Implementierung besteht die zusätzliche Einschränkung darin, dass sie nur dann ein korrektes Ergebnis liefern, wenn Sum of all given numbers<=MAXIMUM_NUMBER_VALUE.)

  3. Berechnen Sie die Gesamtsumme aller Zahlen (einschließlich der unbekannten fehlenden Zahl) und subtrahieren Sie jede gegebene Zahl in derselben Schleife parallel. Dies eliminiert das Risiko eines Bitüberlaufs durch Multiplikation, ist jedoch anfällig für einen Bitüberlauf durch Addition und Subtraktion.

    //ALGORITHM missingNumber = 0; foreach(index from 1 to N) { missingNumber = missingNumber + index; //Since, the empty slot is filled with 0, //this extra condition which is executed for N times is not required. //But for the sake of understanding of algorithm purpose lets put it. if (inputArray[index] != 0) missingNumber = missingNumber - inputArray[index]; }

Wenn in einer Programmiersprache (wie C, C++, Java usw.) die Anzahl der Bits, die einen ganzzahligen Datentyp darstellen, begrenzt ist, neigen alle obigen Implementierungen aufgrund von Summation, Subtraktion und Multiplikation zum Bitüberlauf, was zu einem falschen Ergebnis führt im Falle von großen Eingabewerten (A[1...N]) und/oder einer großen Anzahl von Eingabewerten (N).

Algorithmus 2:

Wir können die Eigenschaft von XOR verwenden, um eine Lösung für dieses Problem zu erhalten, ohne uns um das Problem des Bitüberlaufs kümmern zu müssen. Außerdem ist XOR sowohl sicherer als auch schneller als die Summierung. Wir kennen die Eigenschaft von XOR, dass XOR von zwei gleichen Zahlen gleich 0 ist (A XOR A = 0). Wenn wir XOR aller Zahlen von 1 bis N berechnen (dies schließt die unbekannte fehlende Zahl ein) und dann mit diesem Ergebnis XOR alle gegebenen Zahlen, werden die gemeinsamen Zahlen gelöscht out (seit A XOR A=0) und am Ende bekommen wir die fehlende Nummer. Wenn wir kein Bitüberlaufproblem haben, können wir sowohl Summations- als auch XOR-basierte Algorithmen verwenden, um die Lösung zu erhalten. Der Algorithmus, der XOR verwendet, ist jedoch sowohl sicherer als auch schneller als der Algorithmus, der Summation, Subtraktion und Multiplikation verwendet. Und wir können die zusätzlichen Sorgen vermeiden, die durch Summation, Subtraktion und Multiplikation verursacht werden.

In allen Implementierungen von Algorithmus 1 können wir XOR anstelle von Addition und Subtraktion verwenden.

Nehmen wir an, XOR(1...N) = XOR of all numbers from 1 to N

Implementierung 1 => Missing Number = XOR(1...N) XOR (A[1] XOR A[2] XOR...XOR A[100])

Implementierung 2 => Missing Number = XOR(1...N) XOR A[1] XOR A[2] XOR...XOR A[100]

Implementierung 3 =>

//ALGORITHM
missingNumber = 0;
foreach(index from 1 to N)
{
    missingNumber = missingNumber XOR index;
    //Since, the empty slot is filled with 0,
    //this extra condition which is executed for N times is not required.
    //But for the sake of understanding of algorithm purpose lets put it.
    if (inputArray[index] != 0)
        missingNumber = missingNumber XOR inputArray[index];
}

Alle drei Implementierungen von Algorithmus 2 werden gut funktionieren (auch aus programmatischer Sicht). Eine Optimierung ist ähnlich wie

1+2+....+N = (N(N+1))/2

Wir haben,

1 XOR 2 XOR .... XOR N = {N if REMAINDER(N/4)=0, 1 if REMAINDER(N/4)=1, N+1 if REMAINDER(N/4)=2, 0 if REMAINDER(N/4)=3}

Wir können dies durch mathematische Induktion beweisen. Anstatt den Wert von XOR (1 ... N) durch XOR alle Zahlen von 1 bis N zu berechnen, können wir diese Formel verwenden, um die Anzahl von XOR Operationen zu reduzieren .

Die Berechnung von XOR (1 ... N) unter Verwendung der obigen Formel hat zwei Implementierungen. Implementierung klug, berechnend

// Thanks to https://a3nm.net/blog/xor.html for this implementation
xor = (n>>1)&1 ^ (((n&1)>0)?1:n)

ist schneller als rechnen

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

Der optimierte Java Code lautet also:

long n = 100;
long a[] = new long[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

//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);
long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

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

Dies war eine Amazon-Interview-Frage, die ursprünglich hier beantwortet wurde: Wir haben Zahlen von 1 bis 52, die in einem 51-Zahlen-Array angeordnet sind. Wie kann ich herausfinden, welche Nummer fehlt?

Es wurde wie folgt beantwortet:

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.

Es wurde auch hier gebloggt: Software-Job - Interview-Frage

17
bchetty

Hier ist ein einfaches Programm, um die fehlenden Zahlen in einem Integer-Array zu finden

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

5050 - (Summe aller Werte im Array) = fehlende Zahl

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

In einem ähnlichen Szenario bei dem das Array bereits sortiert ist enthält es keine Duplikate, und es fehlt nur eine Nummer. Diese fehlende Nummer kann in log (n) time gefunden werden .

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
}

Verwenden Sie einen Blütenfilter.

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

Die Lösung, die keine wiederholten Hinzufügungen oder möglicherweise die Formel n (n + 1)/2 beinhaltet, wird Ihnen beispielsweise zu einem Interview nicht angezeigt.

Sie müssen ein Array von 4 Ints (32 Bit) oder 2 Ints (64 Bit) verwenden. Initialisieren Sie das letzte int mit (-1 & ~ (1 << 31)) >> 3. (Die Bits, die über 100 liegen, werden auf 1 gesetzt.) Oder Sie können die Bits über eine for-Schleife über 100 setzen.

  1. Durchsuchen Sie das Zahlenfeld und setzen Sie 1 für die Bitposition, die der Zahl entspricht (z. B. würde 71 auf das 3. int des 7. Bits von links nach rechts gesetzt).
  2. Durchlaufen Sie das Array mit 4 Ints (32-Bit-Version) oder 2 Ints (64-Bit-Version).

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

Beispiel: (32-Bit-Version) sagen wir, dass die fehlende Zahl 58 ist. Das bedeutet, dass das 26. Bit (von links nach rechts) der zweiten Ganzzahl auf 0 gesetzt ist.

Das erste int ist -1 (alle Bits sind gesetzt), also fahren wir mit dem zweiten fort und addieren die Zahl 32 zu "Nein". Das zweite int unterscheidet sich von -1 (ein Bit ist nicht gesetzt), also durch Anwenden der Operator NOT (~) für die Zahl, die wir 64 erhalten. Die möglichen Zahlen sind 2 bei der Potenz x, und wir können x unter Verwendung von log on base 2 berechnen. In diesem Fall erhalten wir log2 (64) = 6 => 32 + 32 - 6 = 58.

Hoffe das hilft.

2
MARIU5

Dies ist c #, aber es sollte ziemlich nahe an dem sein, was Sie brauchen:

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;
2
Martin Booth

Ich habe diese schöne Lösung hier gefunden: 

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
Bhavin Shah

Ich denke, die einfachste und möglicherweise effizienteste Lösung wäre, alle Einträge zu durchlaufen und ein Bitset zu verwenden, um sich zu merken, welche Zahlen gesetzt sind, und dann auf 0-Bit zu testen. Der Eintrag mit dem 0-Bit ist die fehlende Zahl.

1
Tushar Gupta

Dies ist kein Suchproblem. Der Arbeitgeber fragt sich, ob Sie eine Prüfsumme haben. Sie benötigen möglicherweise eine Binär- oder for-Schleife oder was auch immer, wenn Sie nach mehreren eindeutigen Ganzzahlen suchen, aber die Frage lautet "ein zufälliger leerer Slot". In diesem Fall können wir die Stromsumme verwenden. Die Bedingung: "Die Zahlen werden zufällig dem Array hinzugefügt" ist ohne weitere Details bedeutungslos. Die Frage geht nicht davon aus, dass das Array mit der Ganzzahl 1 beginnen muss und daher mit der Ganzzahl des Offset-Starts toleriert wird. 

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

Erfolgszeit: 0,18 Speicher: 320576 Signal: 0

1
Radio

Vor kurzem hatte ich eine ähnliche (nicht genau die gleiche) Frage in einem Vorstellungsgespräch, und ich hörte auch von einem Freund, dem in einem Interview genau dieselbe Frage gestellt wurde. .__ Hier also eine Antwort auf die OP-Frage und ein paar weitere Variationen, die möglicherweise abgefragt werden können. .__ Die Antwortbeispiele sind in Java angegeben, da Folgendes angegeben ist:

Eine Java-Lösung ist vorzuziehen.

Lösung 1:

Zahlenarray von 1 bis 100 (beide inklusive) ... Die Zahlen werden dem Array zufällig hinzugefügt, aber es gibt einen zufälligen leeren Platz im Array

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

Explanation: Diese Lösung (wie viele andere hier veröffentlichte Lösungen) basiert auf der Formel Triangular number , die uns die Summe aller natürlichen Zahlen von 1 bis n (in diesem Fall n) ergibt 100). Nun, da wir die Summe kennen, die zwischen 1 und 100 liegen sollte, müssen wir nur die tatsächliche Summe der vorhandenen Zahlen in einem gegebenen Feld abziehen. 

Lösung 2:

Zahlenfeld von 1 bis n (bedeutet, dass die maximale Anzahl unbekannt ist) 

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

Erläuterung: Da bei dieser Lösung die maximale Anzahl nicht angegeben ist, müssen wir sie finden. Nachdem Sie die maximale Anzahl gefunden haben, ist die Logik dieselbe. 

Lösung 3:

Array von Zahlen von 1 bis n (maximale Anzahl ist unbekannt), es gibt zwei zufällige leere Slots im Array 

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

Erläuterung: In dieser Lösung wird die maximale Anzahl nicht angegeben (wie in der vorherigen), es können jedoch auch zwei Zahlen und keine eine fehlen. Zuerst finden wir die Summe der fehlenden Zahlen - mit derselben Logik wie zuvor. Zweite Ermittlung der kleineren Zahl zwischen fehlender Summe und der letzten (möglicherweise) fehlenden Zahl, um unnötige Suchvorgänge zu vermeiden. Drittens, da Javas Array (keine Collection) keine Methoden als indexOf oder contains hat, habe ich eine kleine wiederverwendbare Methode für diese Logik hinzugefügt. Viertens, wenn die erste fehlende Zahl gefunden wird, wird die zweite von der fehlenden Summe abgezogen. Wenn nur eine Zahl fehlt, ist die zweite Zahl im Feld Null. 

Hinweis

Wenn Sie Beispiele in anderen Sprachen oder anderen interessanten Variationen dieser Frage wünschen, können Sie in meinem Github-Repository nach Interviewfragen & Antworten suchen.

1
Nikita Kurtin

Finden der fehlenden Nummer aus einer Reihe von Zahlen. IMP-Punkte zum Erinnern.

  1. das Array sollte sortiert sein ..
  2. die Funktion funktioniert nicht bei mehreren Fehlschlägen. 
  3. die Sequenz muss ein AP sein. 

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

}
}
0

Eine Sache, die Sie tun können, ist die Sortierung der Zahlen, zum Beispiel durch eine schnelle Sortierung. Verwenden Sie dann eine for-Schleife, um das sortierte Array von 1 bis 100 zu durchlaufen. Bei jeder Iteration vergleichen Sie die Nummer im Array mit Ihrem for-Loop-Inkrement, wenn Sie feststellen, dass das Index-Increment nicht mit dem Array-Wert übereinstimmt habe Ihre fehlende Nummer sowie den fehlenden Index gefunden. 

0
Stranger

Summenformel verwenden,

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

Referenz http://www.geeksforgeeks.org/find-the-missing-number/

0
Anil Nivargi

Nehmen wir an, Sie haben n als 8, und unsere Zahlen reichen von 0-8 für dieses Beispiel Wir können die binäre Darstellung aller 9 Zahlen wie folgt darstellen 0000 0001 0010 0011 0100 0101 0101 0111 1000

in der obigen Reihenfolge gibt es keine fehlenden Zahlen und in jeder Spalte stimmen die Anzahl der Nullen und Einsen überein. Sobald Sie jedoch 1 Wert entfernen, sagen wir 3, erhalten wir ein Gleichgewicht in der Anzahl der 0 und 1 über die Spalten. Wenn die Anzahl der Nullen in einer Spalte <= Anzahl der Einsen ist, wird unsere fehlende Zahl an dieser Bitposition eine 0 haben. Andernfalls, wenn die Anzahl der Nullen> die Anzahl der Einsen an dieser Bitposition ist, wird diese Bitposition eine 1 sein Wir testen die Bits von links nach rechts und bei jeder Iteration werfen wir die Hälfte des Arrays weg, um das nächste Bit zu testen. Entweder die ungeraden Arraywerte oder die geraden Arraywerte werden bei jeder Iteration weggeworfen, abhängig davon, welches Bit uns fehlt auf. 

Die folgende Lösung ist in 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;
}

Bei jeder Iteration reduzieren wir unseren Eingaberaum um 2, d. H. N, N/2, N/4 ... = O (log N), mit Leerzeichen 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
0
gilla07

======== Einfachste Lösung für sortiertes Array ===========

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;
        }
0
Sony Khan

Im Folgenden finden Sie die Lösung, um alle fehlenden Zahlen eines gegebenen Arrays zu finden:

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

}
0
Bhumik Thakkar

Dieses Programm findet fehlende Nummern

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

}
?>
0
Nitesh

Lösung mit PHP $ n = 100 ;

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

und array_search($missing_number) gibt den Index der fehlenden Nummer an

Hier nimmt das Programm Zeit in Anspruch, Komplexität ist O(logn) und Speicherplatzkomplexität 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);

  }
 }
0
brahmananda Kar
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);
  }
} 
0
Ashish168
function solution($A) {
    // code in PHP5.5
    $n=count($A);
    for($i=1;$i<=$n;$i++) {
       if(!in_array($i,$A)) {
              return (int)$i;
       }
    }
}
0
Shiv Kumar Sah