Liste der verbleibenden Nummern generieren

Question

Gegeben eine Zahl n und ein Array mit der Größe m wobei m < n. Vorausgesetzt, dass jede Zahl im Array zwischen 0 und n-1 (inklusive) liegt, möchte ich so effizient wie möglich die Liste der n-m Zahlen von 0 bis n-1 erhalten, die nicht im Array sind.

Das ist, wie ich es tue (in Pseudo-Code), aber es fühlt sich eher ineffizient und ich frage mich, ob es einen besseren Weg:

int[] remaining (int[] assigned) { 
    Set<int> s 
    int[n-m] remaining 
    add each int in assigned to s 
    for(i = 0 to n-1) 
     if(not s.contains(i)) remaining.add(i); 
} 

Dies ist keine bestimmte Sprache Computer, aber es sollte sei illusorisch. Wir gehen davon aus, dass der Zugriff auf ein Array natürlich O (1) ist und das Hinzufügen/Überprüfen eines Satzes ist O (log (n)), wie es ein AVL-Satz wäre. Ich versuche also, dies in linearer Zeit zu erreichen, anstatt in O (n · logn), wie es jetzt ist, aber wenn das ursprüngliche Array nicht sortiert ist, weiß ich nicht, wie ich es anstellen soll oder ob es überhaupt möglich ist .

Answer 1

ich denke, es wäre auch

int[] remaining (int[] assigned) { 
    Set<int> s 
    int[n] all 
    int[n-m] remaining 
    for(i = 0 to m-1) 
     all[assigned[i]]=-1 
    int counter=0 
    for(i = 0 to n-1) 
     if (all[i]==-1) 
      remaining[counter]=all[i] 
      counter++ 
    return remaining 
} 

Answer 2

Kopieren Sie das Array in eine hashmap H. Dies dauert O(m).

for i from 0 to n-1 
    if(H.ispresent(i) == FALSE) 
     output i 

Diese For-Schleife dauert O(n). Wie n>=m die Gesamtkomplexität ist O(n)

Answer 3

Die bitset (Bit-Array) Idee:

#include <iostream> 
#include <fstream> 
#include <bitset> 

const int SIZE = 10; // for example 

int main() { 
    std::bitset<SIZE> bs; 
    int i; 

    std::ifstream fin("numbers.txt"); 
    while (fin >> i) 
     bs.set(i); 
    fin.close(); 

    for (i = 0; i < SIZE; ++i) 
     if (!bs[i]) 
      std::cout << i << '\n'; 

    return 0; 
} 

Answer 4

Wenn Sie müssen ein wenig schneller Pseudo-Code sein finden 1 oder 2 fehlende Zahlen, können Sie immer die Summe und/oder das Produkt der Zahlen verwenden, um die fehlenden Zahlen herauszufinden. Wenn es mehr als 2

ist

Code für die Verwendung eines Bitsets in Java, um die fehlenden Zahlen zu finden.

/* Sie können auch durch die Liste interagieren und später das MANUM finden. Das Bitset basiert auf Vektor und kann größer werden */ if (input == null || input.size() == 0) return null;

BitSet existSet=new BitSet(maxNum); 
for(int val:input){ 
    existSet.set(val); 
} 

List<Integer> missingNum=new ArrayList<Integer>(); 
for(int i=0;i<existSet.length()){ 
    nextIndex=bitSet.nextClearBit(); 
    if(nextIndex==-1) 
     break; 
    missingNum.add(nextIndex); 
    index=nextIndex+1; 

} 
return missingNum; 

}