Genera un elenco di numeri rimanenti

Question

Dato un numero n, e un array con dimensione m dove m < n. A condizione che ogni numero nell'array sia compreso tra 0 e n-1 (inclusi), voglio ottenere il più efficientemente possibile l'elenco di numeri n-m da 0 a n-1 che non sono nell'array.

Ecco come lo sto facendo (in pseudocodice), ma ci si sente piuttosto inefficiente e mi chiedo se c'è un modo migliore:

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

Questo non è un qualsiasi linguaggio di programmazione particolare, ma esso dovrebbe essere ilustrativo Assumiamo che l'accesso a un array sia ovviamente O (1) e l'aggiunta/verifica di un set è O (log (n)) come sarebbe un set AVL. Quindi in pratica sto cercando di ottenere questo in tempo lineare, invece di O (n · logn) come ora, ma se l'array iniziale non è ordinato non so come farlo, o se è possibile anche .

Answer 1

penso che sarebbe un po 'più veloce pseudocodice anche

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

copia la matrice in una hashmap H. Questo richiede O(m).

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

Questo ciclo prende O(n). Come n>=m la complessità generale è O(n)

Answer 3

Il bitset (bit array) idea:

#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

Se dovete trovare 1 o 2 numeri mancanti, puoi sempre usare la somma e/o il prodotto dei numeri per capire i numeri mancanti. Se è più di 2

Codice per l'utilizzo di un Bitset in java per trovare i numeri mancanti.

public List<Integer> findMissingNumbers(List<Integer> input,int maxNum){ 

/* È inoltre possibile interate l'elenco e trovare il manum più tardi. Il bitset si basa sul vettore e può aumentare di dimensioni */ 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; 

}