나머지 숫자 목록 생성

Question

주어진 숫자 n 및 크기가 m 인 배열은 m < n입니다. 배열의 각 숫자가 0과 n-1 (포함) 사이에 있으면 배열에없는 0에서 n-1까지의 n-m 숫자 목록을 최대한 효율적으로 가져 오려고합니다.

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

이 특정 컴퓨터 언어가 아니라 그것을해야한다 : 나는 (의사 코드)를하고 있어요,하지만 오히려 비효율적 인 느낌과 더 나은 방법이 있는지 궁금 해요 방법

낫다. 우리는 배열에 접근하는 것은 당연히 O (1)이고, AVL 세트가 될 때 세트를 추가/체크하는 것은 O (log (n))라고 가정합니다. 그래서 기본적으로 지금처럼 O (n • logn) 대신에 선형 시간에 이것을 얻으려고합니다.하지만 초기 배열이 정렬되어 있지 않다면 어떻게 할 것인지, 아니면 가능할 지 모르겠습니다. .

Answer 1

내가 조금 더 빨리 의사 찾을해야하는 경우도

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

배열을 해시맵 H에 복사하십시오. 이 작업에는 O(m)이 필요합니다.

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

for 루프는 O(n)입니다. n>=m으로 전체 복잡성은 O(n)

Answer 3

비트 세트 (비트 배열) 아이디어 :

#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

있을 거라고 생각 1 또는 2 개의 누락 된 숫자가 있으면 누락 된 숫자를 계산할 때 숫자의 합 및/또는 곱을 항상 사용할 수 있습니다 .2 이상인 경우

Java에서 Bitset을 사용하여 누락 된 번호를 찾는 코드입니다.

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

/* 또한 목록을 검토하고 나중에 maNum을 찾을 수도 있습니다. 비트 집합은 벡터를 기반으로하므로 크기가 커질 수 있습니다. */ 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; 

}