배열의 숫자와 다른 숫자를 생성하십시오.

Question

1000 개의 큰 숫자 (1000 개의 요소 공간 이상) (64 비트 숫자도 가능)가 있습니다. 배열의 숫자가 반드시 정렬되지 않을 수도 있습니다.
이전의 1000과 다른 1001 번째 위치에 고유 번호를 생성해야합니다.
사용 된 접근 방식을 정당화하는 것이 가장 좋습니다.

내 대답 (이것이 어느 정도까지 정확한지 알 수 없음) : 숫자를 정렬하고 0 위치부터 시작하십시오. 1000 위 + 1에있는 숫자가 필수 숫자입니다.

더 나은 제안이 있나요?

Answer 1

1001 개 요소의 보조 배열을 만듭니다. 이 모든 것을 1 (또는 참 또는 Y 또는 무엇을 선택 하든지)로 설정하십시오. 주 어레이를 통해 실행하십시오. 1..1000 범위의 숫자를 찾은 다음 보조 배열의 해당 요소를 0으로 설정하거나 다른 방법으로 변조합니다. 마지막에 0 (또는 false)이 아닌 보조 배열의 첫 번째 요소는 주 배열에없는 숫자에 해당합니다.

이것은 간단하며 시간 복잡도의 O (n)입니다. 여기서 n은 주 배열의 요소 수입니다.

Answer 2

unsigned ii,slot; 

unsigned array [ NNN ]; 
/* allocate a histogram */ 
#define XXX (NNN+1); 
unsigned histogram [XXX]; 
memset(histogram, 0, sizeof histogram); 

for (ii=0; ii < NNN; ii++) { 
     slot = array [ii ] % XXX; 
     histogram[slot] += 1; 
     } 
for (slot=0; slot < NNN; slot++) { 
     if (!histogram[slot]) break; 
     } 

/* Now, slot + k * XXX will be a 
** number that does not occur in the original array */ 

참고 :이 마크 고성능과 유사하지만, 적어도 나는 당신이 당신의 배열을 정렬하는 경우 고유 번호에 대한 세 가지 가능성이

Answer 3

... 코드에 입력 :

을

1. 어레이 [999] +1, 어레이 [999]
2. 배열 INT_MAX 같지 않으면 [0] -1, 어레이 [0] 배열 사이
3. 다수 INT_MIN 같지 않으면 [I] 및 배열 [i + 1], arr ay [i + 1] -Array [i]> 1 (0 < = i < = 998)이다. 두 번의 이전 시도가 실패한 경우 배열에 두 요소 사이에 숫자가 있음을 알 수 있습니다.

이 솔루션은 1002 번째, 1003 번째 등의 경우에도 작동합니다.

Answer 4

나는이 문제에 대한 몇 가지 생각이 서투른 C#을 구현

public class Test 
{ 
    public List<int> Sequence { get; set; } 

    public void GenerateFirstSequence() 
    { 
     Sequence = new List<int>(); 
     for (var i = 0; i < 1000; i++) 
     { 
      var x = new Random().Next(0, int.MaxValue); 
      while (Sequence.Contains(x)) 
      { 
       x = new Random().Next(0, int.MaxValue); 
      } 
      Sequence.Add(x); 
     } 
    } 

    public int GetNumberNotInSequence() 
    { 
     var number = Sequence.OrderBy(x => x).Max(); 
     var mustRedefine = number == int.MaxValue && Sequence.Contains(number); 
     if (mustRedefine) 
     { 
      while (Sequence.Contains(number)) 
      { 
       number = number - 1; 
       if (!Sequence.Contains(number)) 
        return number; 
      } 
     } 
     return number + 1; 
    } 
} 

Answer 5

에서 시도 :

당신은 해시 테이블 H를 만들 수 1000 개 요소가 포함되어 있습니다. 배열 이름이 A이고 각 요소에 대해 1000 : m [i] = A [i] % 1000의 미리 알림이 있습니다.

A [i]와 A [j] 사이에 충돌이있는 경우 즉, 인덱스 k가 존재해야합니다. 즉, 요소 ​​미리 알림이 1000으로 k와 같지 않으면 k는 얻으려고하는 숫자입니다. 즉, A [i] % 1000 = A [j] % 1000입니다.

전혀 충돌이 없다면 H [1] + 1000을 결과로 선택하십시오. 이 알고리즘의

복잡도는 L에 원래 목록 사이즈 = 1000