Tạo danh sách các số còn lại

Question

Cho số n và một mảng có kích thước m, trong đó m < n. Với điều kiện là mỗi số trong mảng nằm trong khoảng từ 0 đến n-1 (bao gồm), tôi muốn nhận được càng nhiều càng tốt danh sách các số n-m từ 0 đến n-1 không nằm trong mảng.

Đó là cách tôi đang làm nó (trong giả), nhưng nó cảm thấy khá hiệu quả và tôi tự hỏi nếu có một cách tốt hơn:

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

Đây không phải là bất kỳ ngôn ngữ máy tính cụ thể nhưng nó nên bất lịch sự. Chúng tôi giả định rằng việc truy cập vào một mảng là tất nhiên O (1) và thêm/kiểm tra một bộ là O (log (n)) như là một tập AVL sẽ được. Vì vậy, về cơ bản tôi đang cố gắng để có được điều này trong thời gian tuyến tính, thay vì O (n · logn) như bây giờ, nhưng nếu mảng ban đầu không được sắp xếp tôi không biết làm thế nào để đi về nó, hoặc nếu nó thậm chí có thể .

Answer 1

Tôi nghĩ rằng nó sẽ nhanh hơn một chút giả cũng

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

sao chép mảng vào một bản đồ băm H. Điều này mất O(m).

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

Vòng lặp này mất O(n). Như n>=m tổng thể mức độ phức tạp là O(n)

Answer 3

Các bitset (bit mảng) ý tưởng:

#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

Nếu bạn phải tìm 1 hoặc 2 số bị thiếu, bạn luôn có thể sử dụng tổng và/hoặc sản phẩm của các số để tìm ra các số bị thiếu. Nếu số lớn hơn 2

Mã để sử dụng Bitset trong java để tìm số bị thiếu.

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

/* Bạn cũng có thể liên lạc qua danh sách và tìm maNum sau. Các bitet dựa trên vector và có thể tăng kích thước */ nếu (input == null || input.size() == 0) trả về 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; 

}