[arrays] 목록에없는 가장 작은 정수 찾기

Program / 글쓴이

제 동료가 사용하는 흥미로운 인터뷰 질문 :

부호없는 64 비트 정수의 매우 길고 정렬되지 않은 목록이 제공되었다고 가정하십시오. 목록에 없는 가장 작은 음이 아닌 정수를 어떻게 찾을 수 있습니까?

FOLLOW-UP : 이제 분류에 의한 명백한 해결책이 제안되었으므로 O (n log n)보다 빠르게 할 수 있습니까?

후속 조치 : 알고리즘은 1GB 메모리가있는 컴퓨터에서 실행되어야합니다.

설명 :이 목록은 많은 양을 소비 할 수 있지만 RAM에 있습니다. 목록의 크기 (예 : N)가 미리 제공됩니다.

답변

데이터 구조가 제자리에서 변경 될 수 있고 임의 액세스를 지원하는 경우 O (N) 시간 및 O (1) 추가 공간에서 수행 할 수 있습니다. 배열을 순차적으로 살펴보고 모든 인덱스에 대해 인덱스의 값을 값으로 지정된 인덱스에 쓰고 해당 위치의 값을 해당 위치에 재귀 적으로 배치하고 값> N을 버립니다. 그런 다음 다시 배열을 통해 스팟을 찾습니다. 값이 인덱스와 일치하지 않는 경우-배열에없는 가장 작은 값입니다. 이로 인해 최대 3N 비교가 수행되고 임시 공간에 해당하는 몇 가지 값만 사용됩니다.

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N

답변

다음 O(N)은 O(N)공간 을 사용 하는 간단한 솔루션입니다 . 입력 목록을 음수가 아닌 숫자로 제한하고 목록에없는 첫 번째 음이 아닌 숫자를 찾고 싶다고 가정합니다.

  1. 목록의 길이를 찾으십시오. 그것은이라고 말할 수 있습니다 N.
  2. Nall로 초기화 된 부울 배열을 할당 합니다 false.
  3. X목록의 각 숫자 에 대해 X보다 작은 경우 배열 N의 X'th요소를로 설정합니다 true.
  4. index 0에서 시작하는 배열을 스캔하여 인 첫 번째 요소를 찾습니다 false. 첫 번째 발견하면 false인덱스를 I, 다음 I답변입니다. 그렇지 않으면 (즉, 모든 요소가있을 때 true) 대답은 N입니다.

실제로 ” N부울 배열 “은 byte또는 int배열 로 표시되는 “비트 맵”또는 “비트 세트”로 인코딩 될 수 있습니다 . 이것은 일반적으로 더 적은 공간 (프로그래밍 언어에 따라 다름)을 사용하고 첫 번째 스캔이 false더 빨리 수행되도록합니다.

이것이 알고리즘이 작동하는 방법 / 이유입니다.

N목록 의 숫자가 구별되지 않거나 그 중 하나 이상이보다 크다고 가정 N합니다. 이는 목록에없는 범위에 숫자가 하나 이상 있어야 함을 의미 0 .. N - 1합니다. 따라서 가장 작은 결측 수를 찾는 문제는 따라서 보다N 작은 결측 수를 찾는 문제로 축소되어야합니다 . 이것은 N… 보다 크거나 같은 숫자를 추적 할 필요가 없다는 것을 의미합니다 . 왜냐하면 그들은 답이 될 수 없기 때문입니다.

이전 단락의 대안은 목록이에서 번호의 순열이라는 것입니다 0 .. N - 1. 이 경우 3 단계에서는 배열의 모든 요소를로 설정하고 true4 단계에서는 첫 번째 “누락 된”숫자가 N입니다.

알고리즘의 계산 복잡성은 O(N)상대적으로 작은 비례 상수를 갖습니다. 목록을 두 번의 선형 전달하거나 목록 길이가 시작하는 것으로 알려진 경우 한 번만 전달합니다. 전체 목록을 메모리에 저장할 필요가 없습니다. 따라서 알고리즘의 점근 적 메모리 사용량은 부울 배열을 나타내는 데 필요한 것입니다. 즉 O(N)비트.

(반대로, 메모리 내 정렬 또는 분할에 의존하는 알고리즘은 전체 목록을 메모리에 표시 할 수 있다고 가정합니다. 질문 형식에서는 O(N)64 비트 단어 가 필요합니다 .)

1 ~ 3 단계의 @Jorn 주석은 계산 정렬의 변형입니다. 어떤 의미에서 그는 옳지 만 차이점은 중요합니다.

  • 계수 정렬에는 목록에서 가장 큰 숫자이고 목록 에서 가장 작은 숫자 인 (적어도) Xmax - Xmin카운터 배열이 필요 합니다. 각 카운터는 N 개의 상태를 나타낼 수 있어야합니다. 즉, 이진 표현을 가정하면 정수 유형 (적어도) 비트 가 있어야 합니다.XmaxXminceiling(log2(N))
  • 배열 크기를 결정하려면 계수 정렬을 통해 목록을 처음으로 통과하여 Xmax및 을 결정해야합니다 Xmin.
  • 따라서 최소 최악의 경우 공간 요구 사항은 ceiling(log2(N)) * (Xmax - Xmin)비트입니다.

대조적으로, 위에 제시된 알고리즘은 단순히 N최악의 경우와 최상의 경우의 비트를 필요로합니다 .

그러나이 분석은 알고리즘이 목록을 처음으로 통과하여 0을 찾고 (필요한 경우 목록 요소를 세는 경우) 0을 찾으면 공백을 사용하지 않고 더 빠른 응답을 제공한다는 직관으로 이어집니다. 목록에서 하나 이상의 0을 찾을 가능성이 높은 경우이 작업을 수행 할 가치가 있습니다. 그리고이 추가 패스는 전반적인 복잡성을 변경하지 않습니다.

편집 : 사람들이 비트와 비트 맵을 사용하는 내 원래 설명이 혼란스러워 보이기 때문에 “부울 배열”을 사용하도록 알고리즘 설명을 변경했습니다.

답변

OP는 이제 원래 목록이 RAM에 있고 컴퓨터에 1GB의 메모리 만 있다고 지정 했으므로 팔다리로 나가 대답이 0이라고 예측할 것입니다.

1GB RAM은 목록에 최대 134,217,728 개의 숫자를 포함 할 수 있음을 의미합니다. 그러나 2 64 = 18,446,744,073,709,551,616 개의 가능한 숫자가 있습니다. 따라서 목록에 0이있을 확률은 137,438,953,472 중 1입니다.

대조적으로, 올해 번개 에 맞을 확률은 70 만분의 1입니다. 운석에 맞을 확률 은 약 10 조분의 1입니다. 그래서 저는 답이 0이 아닌 것보다 천체에 의해 제때에 죽지 않아서 과학 저널에 기록 될 가능성이 약 10 배 더 높습니다.

답변

다른 답변에서 지적했듯이 정렬을 수행 한 다음 간격을 찾을 때까지 간단히 스캔 할 수 있습니다.

간격을 포함 할 수있는 잠재적 후보가 아닌 파티션을 제거하는 수정 된 QuickSort를 사용하여 알고리즘 복잡성을 O (N)으로 개선하고 O (N) 공간을 유지할 수 있습니다.

  • 첫 번째 파티션 단계에서 중복을 제거합니다.
  • 분할이 완료되면 하위 파티션의 항목 수를 확인합니다.
  • 이 값이 파티션 생성에 사용 된 값과 같습니까?
    • 그렇다면 더 높은 파티션에 간격이 있음을 의미합니다.
      • 하위 파티션을 무시하고 빠른 정렬을 계속합니다.
    • 그렇지 않으면 간격이 아래쪽 파티션에 있습니다.
      • 상위 파티션을 무시하고 빠른 정렬을 계속합니다.

이것은 많은 계산을 저장합니다.

답변

O(N)사고 의 함정 중 하나를 설명하기 O(N)위해 O(1)공간 을 사용 하는 알고리즘이 있습니다.

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

답변

숫자는 모두 64 비트이므로 기수 정렬 (O (n))을 사용할 수 있습니다 . 정렬 한 다음 원하는 것을 찾을 때까지 스캔하십시오.

가장 작은 숫자가 0이면 간격을 찾을 때까지 앞으로 스캔하십시오. 가장 작은 숫자가 0이 아니면 답은 0입니다.

답변

공간 효율적인 방법과 모든 값이 구별되는 경우 공간 O( k )과 시간 에서 수행 할 수 있습니다 O( k*log(N)*N ). 공간 효율적이고 데이터 이동이 없으며 모든 작업은 기본 (더하기 빼기)입니다.

  1. 세트 U = N; L=0
  2. 먼저 k영역 의 숫자 공간을 분할합니다 . 이렇게 :
    • 0->(1/k)*(U-L) + L, 0->(2/k)*(U-L) + L , 0->(3/k)*(U-L) + L…0->(U-L) + L
  3. count{i}각 지역에 몇 개의 숫자 ( )가 있는지 확인합니다 . ( N*k단계)
  4. 첫 번째 지역 찾기 (h가득 차지 않은 )을 . 즉 count{h} < upper_limit{h}. ( k단계)
  5. h - count{h-1} = 1답이 있다면
  6. 세트 U = count{h}; L = count{h-1}
  7. 2로 이동

이것은 해싱을 사용하여 개선 할 수 있습니다 (Nic이 아이디어에 감사드립니다).

  1. 같은
  2. 먼저 k영역 의 숫자 공간을 분할합니다 . 이렇게 :
    • L + (i/k)->L + (i+1/k)*(U-L)
  3. inc count{j} 사용 j = (number - L)/k (if L < number < U)
  4. 첫 번째 지역 찾기 (hk 요소가없는 )
  5. 만약 count{h} = 1h가 당신의 대답
  6. 세트 U = maximum value in region h L = minimum value in region h

이것은에서 실행됩니다 O(log(N)*N).