쉬운 인터뷰 질문이 더 어려워졌습니다 : 주어진 숫자 1..100, 정확히 주어진 k가없는 누락 된 숫자 찾기
얼마 전 흥미로운 면접 경험이있었습니다. 질문은 정말 쉽게 시작되었습니다.
Q1 : 우리는 숫자가 들어있는 가방을 가지고
1,2,3, ...,100. 각 숫자는 정확히 한 번 나타나므로 100 개의 숫자가 있습니다. 이제 하나의 숫자가 가방에서 무작위로 선택됩니다. 누락 된 번호를 찾으십시오.
물론 이전에이 인터뷰 질문을 들어 본 적이 있으므로 다음과 같이 매우 빠르게 답변했습니다.
A1 : 음, 숫자의 합
1 + 2 + 3 + … + N이다(N+1)(N/2)(참조 : 산술 시리즈의 합을 위키 백과 ). 의 경우N = 100합계는5050입니다.따라서 모든 숫자가 가방에 있으면 합계는 정확히
5050. 하나의 숫자가 누락되었으므로 합계는 이보다 적고 차이는 그 숫자입니다. 그래서 우리는O(N)시간과O(1)공간 에서 그 누락 된 숫자를 찾을 수 있습니다 .
이 시점에서 나는 내가 잘했다고 생각했지만 갑자기 질문이 예상치 못한 방향으로 바뀌었다.
Q2 : 맞습니다 만, 두 개의 숫자가 없으면 어떻게해야합니까?
나는 전에이 변형을 본 적이 / 듣거나 / 고려한 적이 없었기 때문에 당황했고 질문에 대답 할 수 없었다. 면접관이 내 생각 과정을 알고 싶다고 주장했기 때문에 예상되는 제품과 비교해 더 많은 정보를 얻을 수 있다고 말했거나, 아니면 첫 번째 패스에서 정보를 수집 한 후 두 번째 패스를하는 등의 방법으로 더 많은 정보를 얻을 수 있다고 언급했지만 실제로는 촬영 중이었습니다. 실제로 솔루션에 대한 명확한 경로를 갖는 것보다 어둠 속에서.
면접관은 두 번째 방정식을 갖는 것이 실제로 문제를 해결하는 한 가지 방법이라고 말하면서 저를 격려하려고했습니다. 이 시점에서 나는 다소 화가 났고 (사전에 답을 알지 못해서) 이것이 일반적인 ( "유용한") 프로그래밍 기술인지 아니면 단지 속임수 / 잘못된 대답인지 물었습니다.
면접관의 대답에 놀랐습니다.이 기술을 일반화하여 3 개의 누락 된 숫자를 찾을 수 있습니다. 사실, 그것을 일반화하여 k 개의 결측 숫자 를 찾을 수 있습니다.
Qk : 가방에서 정확히 k 개의 숫자가 빠졌다면 어떻게 효율적으로 찾을 수 있을까요?
이것은 몇 달 전이었고 나는이 기술이 무엇인지 여전히 알 수 없었습니다. 분명히 Ω(N)모든 숫자를 한 번 이상 스캔해야하므로 시간 하한이 있지만 면접관 은 해석 기술 의 TIME 및 SPACE 복잡도 ( O(N)시간 입력 스캔 제외)가 N이 아니라 k 로 정의 된다고 주장했습니다 .
따라서 여기서 질문은 간단합니다.
- Q2를 어떻게 해결 하시겠습니까?
- Q3를 어떻게 해결 하시겠습니까?
- Qk를 어떻게 해결 할까요?
설명
- 일반적으로 1..100뿐만 아니라 1 .. N 에서 N 개의 숫자가 있습니다 .
- 예를 들어 비트 세트를 사용하여 지정된 비트의 값으로 각 숫자의 존재 / 부재를 인코딩하여
O(N)추가 공간의 비트를 사용하는 것과 같은 명백한 세트 기반 솔루션을 찾고 있지 않습니다 . N에 비례하는 추가 공간을 감당할 수 없습니다 . - 나는 또한 명백한 정렬 우선 접근 방식을 찾고 있지 않습니다. 이것과 집합 기반 접근 방식은 인터뷰에서 언급 할 가치가 있습니다 (구현하기 쉽고 N 에 따라 매우 실용적 일 수 있음). 저는 성배 솔루션을 찾고 있습니다 (구현하기에는 실용적 일 수도 아닐 수도 있지만 그럼에도 불구하고 원하는 점근 적 특성을 가짐).
다시 말하지만에서 입력을 스캔해야 O(N)하지만 ( N이 아니라 k로 정의 된) 소량의 정보 만 캡처 할 수 있으며 , 그런 다음 어떻게 든 k 개의 누락 된 숫자 를 찾아야합니다 .
다음은 Dimitris Andreou의 링크 요약입니다 .
i 번째 거듭 제곱의 합을 기억하십시오. 여기서 i = 1,2, .., k. 이것은 방정식 시스템을 푸는 문제를 줄입니다.
a 1 + a 2 + ... + a k = b 1
1 2 + A 2 2 + ... + A K 2 = B (2)
...
a 1 k + a 2 k + ... + a k k = b k
Newton의 신원을 사용하여 b i를 알면 다음 을 계산할 수 있습니다.
c 1 = a 1 + a 2 + ... a k
c 2 = a 1 a 2 + a 1 a 3 + ... + a k-1 a k
...
c k = a 1 a 2 ... a k
다항식 (xa 1 ) ... (xa k )을 확장하면 계수는 정확히 c 1 , ..., c k 가됩니다 . Viète의 공식을 참조하십시오 . 모든 다항식 인자가 고유하므로 (다항식의 고리는 유클리드 도메인 ), 이는 i 가 순열까지 고유하게 결정됨을 의미합니다 .
이것은 힘을 기억하는 것이 숫자를 복구하기에 충분하다는 증거를 끝냅니다. 상수 k의 경우 이것은 좋은 접근 방식입니다.
그러나, k가 변할 때, c 1 , ..., c k 계산의 직접적인 접근 은 엄청나게 비싸다. 예를 들어 c k 는 모든 결측 수, 크기 n! / (nk)!의 곱 이기 때문이다 . 이를 극복하려면 Z q field 에서 계산을 수행하십시오 . 여기서 q는 n <= q <2n- Bertrand의 가정에 의해 존재하는 소수 입니다. 공식이 여전히 유지되고 다항식의 분해가 여전히 고유하기 때문에 증명을 변경할 필요가 없습니다. 유한 필드에 대한 인수 분해 알고리즘 (예 : Berlekamp 또는 Cantor-Zassenhaus 의 알고리즘)도 필요합니다 .
상수 k에 대한 높은 수준의 의사 코드 :
- 주어진 숫자의 i 번째 거듭 제곱 계산
- 알 수없는 숫자의 i 번째 거듭 제곱의 합을 구하려면 빼십시오. 합계 b i를 호출하십시오 .
- Newton의 ID를 사용하여 b i 에서 계수를 계산합니다 . 그들을 c i 라고 부르십시오 . 기본적으로 c 1 = b 1 ; c 2 = (c 1 b 1 -b 2 ) / 2; 정확한 공식은 Wikipedia를 참조하십시오.
- 다항식 x k -c 1 x k-1 + ... + c k를 인수 분해 합니다.
- 다항식의 근은 필요한 숫자 a 1 , ..., a k 입니다.
변화하는 k의 경우, 예를 들어 Miller-Rabin을 사용하여 소수 n <= q <2n을 찾고 모듈로 q를 줄인 모든 숫자로 단계를 수행합니다.
편집 :이 답변의 이전 버전은 q가 소수 인 Z q 대신 특성 2 (q = 2 ^ (log n))의 유한 필드를 사용할 수 있다고 명시했습니다 . Newton의 공식은 최대 k까지의 숫자로 나눌 필요가 있기 때문에 이것은 사실이 아닙니다.
Muthukrishnan-Data Stream Algorithms : Puzzle 1 : Finding Missing Numbers 의 두 페이지를 읽으면 찾을 수 있습니다 . 찾고있는 일반화를 정확하게 보여줍니다 . 아마도 이것이 당신의 면접관이 읽은 내용이며 그가 이러한 질문을 제기 한 이유 일 것입니다.
이제 사람들 만 Muthukrishnan의 처리로 포함되거나 대체 된 답변을 삭제하기 시작하고이 텍스트를 더 쉽게 찾을 수 있도록합니다. :)
또한 의사 코드를 포함하는 sdcvvc의 직접 관련된 답변을 참조하십시오 (만세! 까다로운 수학 공식을 읽을 필요가 없습니다 :)) (감사합니다, 훌륭합니다!).
숫자 자체와 숫자의 제곱 을 합하여 Q2를 풀 수 있습니다 .
그런 다음 문제를 다음과 같이 줄일 수 있습니다.
k1 + k2 = x
k1^2 + k2^2 = y
어디 x하고하는 것은 y합계가 예상 값보다 얼마나 멀리 있습니다.
대체하면 다음이 제공됩니다.
(x-k2)^2 + k2^2 = y
그런 다음이를 풀면 누락 된 숫자를 확인할 수 있습니다.
@j_random_hacker가 지적했듯이 이것은 O (n) 시간 및 O (1) 공간에서 중복 찾기 와 매우 유사하며 내 대답의 적응도 여기에서 작동합니다.
"bag"이 1부터 시작 A[]하는 size 배열 로 표현된다고 가정하면 시간과 추가 공간 N - k에서 Qk를 풀 수 있습니다 .O(N)O(k)
먼저 배열 A[]을 k요소 별로 확장 하여 이제 크기가되도록합니다 N. 이것은 O(k)추가 공간입니다. 그런 다음 다음 의사 코드 알고리즘을 실행합니다.
for i := n - k + 1 to n
A[i] := A[1]
end for
for i := 1 to n - k
while A[A[i]] != A[i]
swap(A[i], A[A[i]])
end while
end for
for i := 1 to n
if A[i] != i then
print i
end if
end for
첫 번째 루프는 k추가 항목을 배열의 첫 번째 항목과 동일하게 초기화합니다 (이는 배열에 이미 존재한다는 것을 알고있는 편리한 값일뿐입니다.이 단계 후에 크기의 초기 배열에서 누락 된 항목 N-k은 다음과 같습니다. 여전히 확장 어레이에서 누락 됨).
두 번째 루프 x는 요소 가 한 번 이상 존재하면 해당 항목 중 하나가 위치에 있도록 확장 배열을 순열합니다 A[x].
중첩 루프가 있더라도 여전히 O(N)시간 내에 실행됩니다 . 스왑은 ithat 이있는 경우에만 발생 A[i] != i하고 각 스왑은 A[i] == i이전에 true가 아니었던 해당 요소를 적어도 하나 설정합니다 . 이는 총 스왑 수 (따라서 while루프 본문 의 총 실행 수 )가 최대 N-1.
세 번째 루프 i는 값 i이 차지하지 않는 배열의 인덱스를 인쇄 i합니다. 즉, 누락 되었음 이 분명 합니다.
나는 4 살짜리 아이에게이 문제를 풀도록 요청했습니다. 그는 숫자를 분류하고 함께 세었다. 이것은 O (주방 바닥)의 공간 요구 사항을 가지고 있으며 많은 공이 없어도 쉽게 작동합니다.
이것이 가장 효율적인 솔루션인지 확실하지 않지만 모든 항목을 반복하고 bitset을 사용하여 설정된 숫자를 기억 한 다음 0 비트를 테스트합니다.
나는 간단한 해결책을 좋아합니다. 그리고 그것이 합이나 제곱의 합 등을 계산하는 것보다 빠를 수도 있다고 믿습니다.
나는 수학을 확인하지 않았지만 Σ(n^2)우리가 계산하는 것과 같은 패스에서 계산 Σ(n)하면 두 개의 누락 된 숫자를 얻을 수있는 충분한 정보를 제공 할 것이라고 생각합니다 Σ(n^3). 세 개가 있으면 Do 도 마찬가지입니다.
숫자의 합을 기반으로 한 솔루션의 문제는 큰 지수를 가진 숫자를 저장하고 작업하는 비용을 고려하지 않는다는 것입니다. 실제로 매우 큰 n에서 작동하려면 큰 숫자 라이브러리가 사용됩니다. . 이러한 알고리즘의 공간 활용도를 분석 할 수 있습니다.
sdcvvc 및 Dimitris Andreou 알고리즘의 시간 및 공간 복잡성을 분석 할 수 있습니다.
저장:
l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)
l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`
그래서 l_j \in \Theta(j log n)
사용 된 총 저장 용량 : \sum_{j=1}^k l_j \in \Theta(k^2 log n)
사용 된 공간 : 컴퓨팅에 a^j시간이 걸린다고 가정하면 ceil(log_2 j)총 시간 :
t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n) \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)
총 사용 시간 : \Theta(kn log n)
이 시간과 공간이 만족 스러우면 간단한 재귀 알고리즘을 사용할 수 있습니다. b! i는 백의 i 번째 항목, n은 제거 전 숫자, k는 제거 횟수입니다. Haskell 구문에서 ...
let
-- O(1)
isInRange low high v = (v >= low) && (v <= high)
-- O(n - k)
countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
findMissing l low high krange
-- O(1) if there is nothing to find.
| krange=0 = l
-- O(1) if there is only one possibility.
| low=high = low:l
-- Otherwise total of O(knlog(n)) time
| otherwise =
let
mid = (low + high) `div` 2
klow = countInRange low mid
khigh = krange - klow
in
findMissing (findMissing low mid klow) (mid + 1) high khigh
in
findMising 1 (n - k) k
사용 된 저장소 : O(k)목록 용, O(log(n))스택 용 : O(k + log(n))이 알고리즘은 더 직관적이고 시간이 복잡하며 공간을 덜 사용합니다.
잠시만 요. 질문에서 언급했듯이 가방에는 100 개의 숫자가 있습니다. k가 아무리 크더라도 루프의 최대 100-k 반복에서 집합을 사용하고 집합에서 숫자를 제거 할 수 있기 때문에 문제는 일정한 시간에 해결 될 수 있습니다. 100은 일정합니다. 나머지 숫자 세트가 답입니다.
1에서 N까지의 수에 대한 해를 일반화하면 N이 상수가 아닌 것 외에는 아무것도 변하지 않으므로 O (N-k) = O (N) 시간에 있습니다. 예를 들어, 비트 세트를 사용하는 경우 O (N) 시간에 비트를 1로 설정하고 숫자를 반복하고 (O (Nk) = O (N)) 갈 때 비트를 0으로 설정 한 다음 답이 있습니다.
면접관이 O (N) 시간이 아닌 O (k) 시간에 최종 세트의 내용 을 출력 하는 방법을 묻는 것 같습니다 . 분명히 비트 세트를 사용하면 숫자를 인쇄해야하는지 여부를 결정하기 위해 모든 N 비트를 반복해야합니다. 그러나 집합이 구현되는 방식을 변경하면 k 반복으로 숫자를 인쇄 할 수 있습니다. 이것은 해시 세트와 이중 연결 목록 모두에 저장 될 객체에 숫자를 넣어 수행됩니다. 해시 세트에서 객체를 제거하면 목록에서도 제거됩니다. 답은 이제 길이가 k 인 목록에 남습니다.
누락 된 숫자 2 개 (및 3 개) 문제를 해결하기 위해를 수정할 수 있습니다. quickselect은 평균적으로 실행되며 O(n)파티셔닝이 제자리에서 수행되는 경우 상수 메모리를 사용합니다.
임의의 피벗과 관련하여 집합을 피벗 보다 작은 숫자를 포함하는
p분할l및 피벗보다 큰 숫자를 포함하는 분할로 분할 합니다r.피벗 값을 각 파티션의 크기 (
p - 1 - count(l) = count of missing numbers in l및n - count(r) - p = count of missing numbers in r) 와 비교하여 2 개의 누락 된 숫자가있는 파티션을 확인합니다.a) 각 파티션에 하나의 숫자가 누락 된 경우 합계 차이 접근법을 사용하여 누락 된 각 숫자를 찾습니다.
(1 + 2 + ... + (p-1)) - sum(l) = missing #1과((p+1) + (p+2) ... + n) - sum(r) = missing #2b) 하나의 파티션에 두 숫자가 모두 누락되고 파티션이 비어있는 경우 누락 된 숫자는 숫자 가 누락 된 파티션
(p-1,p-2)또는(p+1,p+2)파티션에 따라 다릅니다.하나의 파티션에 2 개의 숫자가 누락되었지만 비어 있지 않은 경우 해당 파티션으로 재귀합니다.
누락 된 숫자가 2 개 뿐인이 알고리즘은 항상 하나 이상의 파티션을 삭제하므로 O(n)빠른 선택의 평균 시간 복잡성이 유지됩니다. 마찬가지로, 누락 된 숫자가 3 개인 경우이 알고리즘은 각 패스에서 적어도 하나의 파티션을 삭제합니다 (누락 된 숫자가 2 개인 경우와 같이 최대 1 개의 파티션에만 여러 개의 누락 된 숫자가 포함되기 때문). 그러나 누락 된 숫자가 더 추가 될 때 성능이 얼마나 저하되는지 잘 모르겠습니다.
다음은 인플레 이스 파티셔닝을 사용 하지 않는 구현 이므로이 예제는 공간 요구 사항을 충족하지 않지만 알고리즘의 단계를 보여줍니다.
<?php
$list = range(1,100);
unset($list[3]);
unset($list[31]);
findMissing($list,1,100);
function findMissing($list, $min, $max) {
if(empty($list)) {
print_r(range($min, $max));
return;
}
$l = $r = [];
$pivot = array_pop($list);
foreach($list as $number) {
if($number < $pivot) {
$l[] = $number;
}
else {
$r[] = $number;
}
}
if(count($l) == $pivot - $min - 1) {
// only 1 missing number use difference of sums
print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
}
else if(count($l) < $pivot - $min) {
// more than 1 missing number, recurse
findMissing($l, $min, $pivot-1);
}
if(count($r) == $max - $pivot - 1) {
// only 1 missing number use difference of sums
print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
} else if(count($r) < $max - $pivot) {
// mroe than 1 missing number recurse
findMissing($r, $pivot+1, $max);
}
}
여기에 현명한 트릭없이 간단하게 k 비트의 추가 스토리지를 사용하는 솔루션이 있습니다. 실행 시간 O (n), 추가 공간 O (k). 해결책을 먼저 읽거나 천재가되지 않고도이 문제를 해결할 수 있음을 증명하기 위해 :
void puzzle (int* data, int n, bool* extra, int k)
{
// data contains n distinct numbers from 1 to n + k, extra provides
// space for k extra bits.
// Rearrange the array so there are (even) even numbers at the start
// and (odd) odd numbers at the end.
int even = 0, odd = 0;
while (even + odd < n)
{
if (data [even] % 2 == 0) ++even;
else if (data [n - 1 - odd] % 2 == 1) ++odd;
else { int tmp = data [even]; data [even] = data [n - 1 - odd];
data [n - 1 - odd] = tmp; ++even; ++odd; }
}
// Erase the lowest bits of all numbers and set the extra bits to 0.
for (int i = even; i < n; ++i) data [i] -= 1;
for (int i = 0; i < k; ++i) extra [i] = false;
// Set a bit for every number that is present
for (int i = 0; i < n; ++i)
{
int tmp = data [i];
tmp -= (tmp % 2);
if (i >= even) ++tmp;
if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
}
// Print out the missing ones
for (int i = 1; i <= n; ++i)
if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
for (int i = n + 1; i <= n + k; ++i)
if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);
// Restore the lowest bits again.
for (int i = 0; i < n; ++i) {
if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
else { if (data [i] % 2 == 0) data [i] += 1; }
}
}
모든 숫자가 존재하는지 확인할 수 있습니까? 그렇다면 다음을 시도해보십시오.
S = 가방에있는 모든 숫자의 합계 (S <5050)
Z = 누락 된 숫자의 합계 5050-S
누락 된 숫자가 다음 x과 같은 y경우 :
x = Z-y 및
max (x) = Z-1
당신의 범위를 확인 그래서 1로 max(x)하고 번호를 찾을 수
이 알고리즘은 질문 1에서 작동 할 수 있습니다.
- 처음 100 개 정수의 xor 미리 계산 (val = 1 ^ 2 ^ 3 ^ 4 .... 100)
- xor 입력 스트림에서 계속 오는 요소 (val1 = val1 ^ next_input)
- 최종 답변 = val ^ val1
또는 더 나은 :
def GetValue(A)
val=0
for i=1 to 100
do
val=val^i
done
for value in A:
do
val=val^value
done
return val
이 알고리즘은 실제로 두 개의 누락 된 숫자에 대해 확장 될 수 있습니다. 첫 번째 단계는 동일하게 유지됩니다. 두 개의 누락 된 숫자로 GetValue를 호출하면 결과는 a1^a2두 개의 누락 된 숫자가됩니다. 의 말을하자
val = a1^a2
이제 val에서 a1과 a2를 걸러 내기 위해 val에서 임의의 세트 비트를 취합니다. ith비트가 val로 설정 되었다고 가정 해 봅시다. 이는 a1과 a2가 ith비트 위치 에서 다른 패리티를 가지고 있음을 의미합니다 . 이제 원래 배열에서 또 다른 반복을 수행하고 두 개의 xor 값을 유지합니다. 하나는 i 번째 비트가 설정된 숫자이고 다른 하나는 i 번째 비트가 설정되지 않은 숫자입니다. 이제 우리는 두 개의 숫자 버킷을 가지고 a1 and a2있으며 다른 버킷에있을 것입니다. 이제 각 버킷에서 누락 된 요소 하나를 찾기 위해했던 것과 동일한 작업을 반복합니다.
두 목록의 합계와 두 목록의 곱이 있으면 Q2를 풀 수 있습니다.
(l1은 원본, l2는 수정 된 목록)
d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)
산술 시리즈의 합이 첫 번째 항과 마지막 항의 평균의 n 배이기 때문에이를 최적화 할 수 있습니다.
n = len(l1)
d = (n/2)*(n+1) - sum(l2)
이제 우리는 알았습니다 (만약 a와 b가 제거 된 숫자라면) :
a + b = d
a * b = m
따라서 다음과 같이 재정렬 할 수 있습니다.
a = s - b
b * (s - b) = m
그리고 곱하십시오 :
-b^2 + s*b = m
오른쪽이 0이되도록 재정렬합니다.
-b^2 + s*b - m = 0
그런 다음 이차 공식으로 풀 수 있습니다.
b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b
샘플 Python 3 코드 :
from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5
나는 sqrt, reduce 및 sum 함수의 복잡성을 모르기 때문에이 솔루션의 복잡성을 해결할 수 없습니다 (아는 사람이 있다면 아래에 의견을 말하십시오.)
Q2의 경우 이것은 다른 것보다 조금 더 비효율적이지만 여전히 O (N) 런타임이 있고 O (k) 공간을 차지하는 솔루션입니다.
아이디어는 원래 알고리즘을 두 번 실행하는 것입니다. 첫 번째 항목에서는 누락 된 총 숫자를 얻습니다. 이는 누락 된 숫자의 상한을 제공합니다. 이 번호로 전화합시다 N. 누락 된 두 숫자의 합계는 N이므로 첫 번째 숫자는 간격에만있을 수 있고 두 번째 숫자 [1, floor((N-1)/2)]는에있을 수 있습니다 [floor(N/2)+1,N-1].
따라서 모든 숫자를 다시 한 번 반복하여 첫 번째 간격에 포함되지 않은 모든 숫자를 버립니다. 즉, 합계를 추적합니다. 마지막으로, 누락 된 두 숫자 중 하나를 알게되고 두 번째 숫자는 확장됩니다.
이 방법이 일반화 될 수 있고 입력을 한 번 통과하는 동안 여러 검색이 "병렬"로 실행될 수 있다는 느낌이 있지만 아직 방법을 파악하지 못했습니다.
복잡한 수학 방정식과 이론 없이도 가능하다고 생각합니다. 다음은 제자리 및 O (2n) 시간 복잡성 솔루션에 대한 제안입니다.
입력 양식 가정 :
가방에있는 숫자 수 = n
누락 된 숫자 수 = k
가방의 숫자는 길이 n의 배열로 표시됩니다.
algo = n에 대한 입력 배열의 길이
배열에서 누락 된 항목 (백에서 가져온 숫자)은 배열의 첫 번째 요소 값으로 대체됩니다.
예 : 처음에 가방은 [2,9,3,7,8,6,4,5,1,10]처럼 보입니다. 4를 빼면 4의 값은 2 (배열의 첫 번째 요소)가됩니다. 따라서 4 개를 꺼내면 [2,9,3,7,8,6,2,5,1,10]처럼 보입니다.
이 솔루션의 핵심은 배열이 순회 될 때 해당 INDEX의 값을 부정하여 방문한 번호의 INDEX에 태그를 지정하는 것입니다.
IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
{
List<int> missingNumbers = new List<int>();
int arrayLength = arrayOfNumbers.Length;
//First Pass
for (int i = 0; i < arrayLength; i++)
{
int index = Math.Abs(arrayOfNumbers[i]) - 1;
if (index > -1)
{
arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
}
}
//Second Pass to get missing numbers
for (int i = 0; i < arrayLength; i++)
{
//If this index is unvisited, means this is a missing number
if (arrayOfNumbers[i] > 0)
{
missingNumbers.Add(i + 1);
}
}
return missingNumbers;
}
이와 같은 스트리밍 알고리즘을 일반화하는 일반적인 방법이 있습니다. 아이디어는 약간의 무작위 화를 사용하여 k요소를 독립적 인 하위 문제로 '확산'하여 원래 알고리즘이 문제를 해결하는 것입니다. 이 기술은 무엇보다도 희소 신호 재구성에 사용됩니다.
a크기 의 배열을 만듭니다u = k^2.- 어떤 선택 보편적 인 해시 함수를 ,
h : {1,...,n} -> {1,...,u}. ( 곱하기-시프트 처럼 ) - 각각의 경우
i에1, ..., n증가a[h(i)] += i x입력 스트림의 각 숫자 에 대해a[h(x)] -= x.
누락 된 모든 숫자가 다른 버킷으로 해시 된 경우 배열의 0이 아닌 요소에 누락 된 숫자가 포함됩니다.
특정 쌍이 동일한 버킷으로 전송 될 확률 1/u은 범용 해시 함수의 정의 보다 적습니다 . 약 k^2/2쌍이 있으므로 오류 확률은 최대 k^2/2/u=1/2. 즉, 우리는 적어도 50 %의 확률로 성공하고, 우리가 증가하면 우리는 u우리의 기회를 증가시킵니다.
이 알고리즘은 k^2 logn공간의 비트를 사용합니다 ( logn배열 버킷 당 비트 가 필요합니다 .) 이것은 @Dimitris Andreou의 답변에 필요한 공간과 일치합니다 (특히 무작위 화되는 다항 인수 분해의 공간 요구 사항).이 알고리즘도 상수를 갖습니다. k전력 합계의 경우 시간 이 아니라 업데이트 당 시간 입니다.
사실, 주석에 설명 된 트릭을 사용하면 power sum 방법보다 훨씬 효율적일 수 있습니다.
O (k)가 의미하는 바에 대한 설명이 필요할 것입니다.
다음은 임의의 k에 대한 간단한 해결책입니다. 숫자 집합의 각 v에 대해 2 ^ v의 합을 누적합니다. 끝에서 i를 1에서 N으로 반복합니다. 2 ^ i와 함께 비트 AND 처리 된 합계가 0이면 i가 누락됩니다. (또는 수치 적으로 2 ^ i로 나눈 합계의 바닥이 짝수이면 또는 sum modulo 2^(i+1)) < 2^i.)
쉽죠? O (N) 시간, O (1) 저장, 임의 k를 지원합니다.
실제 컴퓨터에서 각각 O (N) 공간이 필요한 엄청난 수를 계산하는 것을 제외하고는. 사실이 솔루션은 비트 벡터와 동일합니다.
그래서 당신은 영리하고 합과 제곱의 합과 큐브의 합을 v ^ k의 합까지 계산하고 결과를 추출하기 위해 멋진 수학을 할 수 있습니다. 그러나 이것들도 큰 숫자이기 때문에 우리가 말하는 추상적 인 작동 모델은 무엇입니까? O (1) 공간에 얼마나 들어가고 필요한 크기의 수를 합산하는 데 얼마나 걸립니까?
아주 좋은 문제입니다. Qk에 대해 설정된 차이를 사용하려고합니다. Ruby에서와 같이 많은 프로그래밍 언어가이를 지원합니다.
missing = (1..100).to_a - bag
아마도 가장 효율적인 솔루션은 아니지만이 경우에 그러한 작업 (알려진 경계, 낮은 경계)에 직면했다면 실생활에서 사용할 것입니다. 숫자 세트가 매우 크면 물론 더 효율적인 알고리즘을 고려할 수 있지만 그때까지는 간단한 솔루션으로 충분할 것입니다.
Bloom Filter를 사용해 볼 수 있습니다. 백에있는 각 숫자를 블룸에 삽입 한 다음 각 숫자를 찾을 수 없다고보고 할 때까지 전체 1-k 세트를 반복합니다. 이것은 모든 시나리오에서 답을 찾지 못할 수도 있지만 충분한 해결책이 될 수 있습니다.
나는 그 질문에 대해 다른 접근 방식을 취하고 면접관이 해결하려는 더 큰 문제에 대한 자세한 내용을 조사합니다. 문제와이를 둘러싼 요구 사항에 따라 분명한 집합 기반 솔루션이 옳을 수 있고 목록을 생성하고 나중에 선택하는 방식은 그렇지 않을 수 있습니다.
예를 들어, 면접관이 n메시지 를 발송하려고 k하는데 회신이되지 않은 것을 알아야하고 n-k회신이 도착한 후 가능한 한 작은 벽시계 시간에 그것을 알아야 할 수 있습니다 . 또한 메시지 채널의 특성이 전체 보어에서 실행 되더라도 마지막 응답이 도착한 후 최종 결과를 생성하는 데 걸리는 시간에 영향을주지 않고 메시지간에 일부 처리를 수행 할 수있는 충분한 시간이 있다고 가정 해 보겠습니다. 그 시간은 각 전송 된 메시지의 식별 패싯을 세트에 삽입하고 각 해당 응답이 도착할 때 삭제하는 데 사용할 수 있습니다. 마지막 응답이 도착하면해야 할 유일한 일은 세트에서 식별자를 제거하는 것입니다.O(log k+1). 그 후 세트에는 k누락 된 요소 목록이 포함되며 추가 처리를 수행 할 필요가 없습니다.
이것은 모든 것이 실행되기 때문에 미리 생성 된 숫자 모음을 일괄 처리하는 가장 빠른 방법은 아닙니다 O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)). 그러나 k(미리 알려지지 않은 경우에도) 모든 값에 대해 작동하며 위의 예에서는 가장 중요한 간격을 최소화하는 방식으로 적용되었습니다.
대칭 (수학 언어의 그룹) 측면에서 생각하여 솔루션에 동기를 부여 할 수 있습니다. 숫자 집합의 순서에 관계없이 답은 동일해야합니다. k누락 된 요소를 결정하는 데 도움이되는 함수 를 사용 하려는 경우 해당 속성이있는 함수 인 대칭을 고려해야합니다. 이 함수 s_1(x) = x_1 + x_2 + ... + x_n는 대칭 함수의 한 예이지만 더 높은 수준의 다른 함수도 있습니다. 특히 기본 대칭 기능을 고려하십시오 . 차수 2의 기본 대칭 함수 s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n는 두 요소의 모든 곱의 합입니다. 3 차 이상의 기본 대칭 함수와 유사합니다. 그들은 분명히 대칭입니다. 또한 모든 대칭 기능을위한 빌딩 블록으로 밝혀졌습니다.
당신은 그것에 주목함으로써 기본 대칭 함수를 만들 수 있습니다 s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1)). s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))한 번에 계산할 수 있도록 더 많은 생각을하게되면 그 점을 확신 할 수 있습니다.
배열에서 누락 된 항목을 어떻게 알 수 있습니까? 다항식 (z-x_1)(z-x_2)...(z-x_n). 0숫자 중 하나라도 입력하면로 평가됩니다 x_i. 다항식을 확장하면 z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n. 기본 대칭 함수도 여기에 나타납니다. 근본에 순열을 적용하면 다항식이 동일하게 유지되어야하므로 놀랍지 않습니다.
그래서 우리는 다항식을 만들고 다른 사람들이 언급했듯이 어떤 숫자가 집합에 없는지 알아 내기 위해 그것을 인수로 만들 수 있습니다.
마지막으로, 많은 수의 메모리 넘침에 대해 우려한다면 (n 번째 대칭 다항식은 순서가 될 것입니다 100!) 100보다 큰 소수 mod p에서 이러한 계산을 수행 할 수 있습니다 p.이 경우 다항식을 평가하고 mod p다시 평가되는 것을 찾습니다. 에 대한 0입력은 일련의 숫자이며, 입력 번호가 설정되지 않을 때 그것이 0이 아닌 값으로 평가할 때. 다른 사람들이 지적 그러나,에 따라 시간에 다항식에서 값을 얻기 위해 k,하지 N, 우리는 다항식 요인에 있습니다 mod p.
또 다른 방법은 잔차 그래프 필터링을 사용하는 것입니다.
1에서 4까지의 숫자가 있고 3이 누락되었다고 가정합니다. 이진 표현은 다음과 같습니다.
1 = 001b, 2 = 010b, 3 = 011b, 4 = 100b
그리고 다음과 같은 흐름 그래프를 만들 수 있습니다.
1
1 -------------> 1
| |
2 | 1 |
0 ---------> 1 ----------> 0 |
| | |
| 1 1 | |
0 ---------> 0 ----------> 0 |
| |
1 | 1 |
1 ---------> 0 -------------> 1
흐름 그래프에는 x 개의 노드가 포함되고 x는 비트 수입니다. 그리고 최대 모서리 수는 (2 * x) -2입니다.
따라서 32 비트 정수의 경우 O (32) 공간 또는 O (1) 공간이 필요합니다.
이제 1,2,4부터 시작하는 각 숫자의 용량을 제거하면 잔차 그래프가 남습니다.
0 ----------> 1 ---------> 1
마지막으로 다음과 같은 루프를 실행합니다.
result = []
for x in range(1,n):
exists_path_in_residual_graph(x)
result.append(x)
이제 결과 result에는 누락되지 않은 숫자 (거짓 긍정)가 포함됩니다. 그러나 누락 된 요소 가있는 경우 k <= (결과 크기) <= nk 입니다.
마지막으로 주어진 목록을 검토하여 결과가 누락되었는지 여부를 표시합니다.
따라서 시간 복잡도는 O (n)입니다.
마지막으로, 노드 복용에 의해 위양성 (및 필요한 공간)의 수를 줄일 수있다 00, 01, 11, 10대신의 0와 1.
임의로 큰 정수에 대한 및 함수를 사용할 수 있다는 점을 감안할 O(k)때 시간 및 O(log(k))공간 알고리즘 이 있다고 생각 합니다.floor(x)log2(x)
당신은이 k비트 긴 정수 (따라서 log8(k)당신이 추가 공간) x^2: 여기서 x하는 것은 당신이 가방에서 볼 수있는 다음 번호입니다, s=1^2+2^2+...이 소요 O(N)(면접관에 대한 문제가되지 않습니다있는) 시간. 결국 당신은 j=floor(log2(s))당신이 찾고있는 가장 큰 숫자 를 얻 습니다. 그런 다음 s=s-j위의 작업을 다시 수행합니다.
for (i = 0 ; i < k ; i++)
{
j = floor(log2(s));
missing[i] = j;
s -= j;
}
이제 일반적으로 2756-비트 정수에 대한 floor 및 log2 함수가 없지만 대신 double에 대한 함수가 있습니다. 그래서? 간단히 말해서 각 2 바이트 (또는 1, 3 또는 4)에 대해 이러한 함수를 사용하여 원하는 숫자를 얻을 수 있지만 이는 O(N)시간 복잡성에 요인을 추가합니다.
이것은 어리석은 것처럼 들릴 수도 있지만, 첫 번째 문제에서 가방에 남아있는 모든 숫자를 실제로 더해 해당 방정식을 사용하여 누락 된 숫자를 찾아야합니다.
따라서 모든 숫자를 볼 수 있으므로 누락 된 숫자를 찾으십시오. 두 개의 숫자가 누락 된 경우에도 마찬가지입니다. 아주 간단하다고 생각합니다. 가방에 남아있는 숫자를 볼 때 방정식을 사용하는 것은 의미가 없습니다.
나는 이것이 다음과 같이 일반화 될 수 있다고 생각합니다.
S, M을 산술 시리즈와 곱셈의 합에 대한 초기 값으로 표시합니다.
S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n
이것을 계산하는 공식에 대해 생각해야하는데 그게 요점이 아닙니다. 어쨌든 하나의 숫자가 없으면 이미 솔루션을 제공 한 것입니다. 그러나 두 개의 숫자가 누락 된 경우 다음과 같이 S1과 M1에 의한 새 합계와 합계 배수를 나타냅니다.
S1 = S - (a + b)....................(1)
Where a and b are the missing numbers.
M1 = M - (a * b)....................(2)
S1, M1, M 및 S를 알고 있으므로 위의 방정식을 풀면 누락 된 숫자 인 a와 b를 찾을 수 있습니다.
이제 세 개의 숫자가 누락되었습니다.
S2 = S - ( a + b + c)....................(1)
Where a and b are the missing numbers.
M2 = M - (a * b * c)....................(2)
이제 미지수는 3이고 풀 수있는 방정식은 두 개뿐입니다.
이것이 효율적인지 여부는 모르지만이 솔루션을 제안하고 싶습니다.
- 100 개 요소의 xor 계산
- 98 개 요소의 xor 계산 (2 개 요소가 제거 된 후)
- 이제 (결과 1) XOR (결과 2)는 두 개의 누락 된 nos i..ea XOR b의 xor를 제공합니다. a와 b가 누락 된 요소 인 경우
4. 일반적인 접근 방식으로 누락 된 No의 합계를 구합니다. sum 공식 diff와 diff가 d라고 가정합시다.
이제 루프를 실행하여 둘 다 [1, 100]에 있고 합계가 d 인 가능한 쌍 (p, q)을 얻습니다.
쌍을 얻을 때 (결과 3) XOR p = q인지 확인하고 만약 그렇다면 우리는 끝났습니다.
내가 틀렸다면 저를 수정하고 이것이 정확하다면 시간 복잡성에 대해서도 언급하십시오.
우리는 대부분의 시간 에 O (log n) 에서 Q1과 Q2 를 할 수 있습니다 .
우리 memory chip가 n수의 배열로 구성되어 있다고 가정합니다 test tubes. 그리고 x시험관 의 숫자 x milliliter는 화학 액체로 표시됩니다 .
우리의 프로세서가 laser light. 레이저를 비추면 길이에 수직으로 모든 튜브를 가로지 릅니다. 약액을 통과 할 때마다 광도가 감소합니다 1. 그리고 특정 밀리리터 표시로 빛을 전달하는 것은 O(1).
이제 우리가 시험관 중앙에 레이저를 비추고 광도의 출력을 얻으면
- 미리 계산 된 값 (누락 된 숫자가 없을 때 계산 됨)과 같으면 누락 된 숫자가보다 큽니다
n/2. - 출력이 더 작 으면보다 작은 결측 수가 하나 이상있는 것
n/2입니다. 광도가1또는 로 감소되었는지 확인할 수도 있습니다2. 그것이 감소1하면 하나의 누락 된 숫자는보다 작고n/2다른 하나는보다 큽니다n/2. 감소2하면 두 숫자 모두보다 작습니다n/2.
위의 과정을 반복해서 문제 영역을 좁힐 수 있습니다. 각 단계에서 도메인을 절반으로 작게 만듭니다. 그리고 마지막으로 결과를 얻을 수 있습니다.
언급 할 가치가있는 병렬 알고리즘 (재미 있기 때문에),
- 예를 들어 병렬 병합은
O(log^3 n)시간 내에 수행 할 수 있습니다 . 그런 다음 이진 검색을 통해 누락 된 숫자를 찾을 수 있습니다O(log n). - 이론적으로
n프로세서 가 있으면 각 프로세스는 입력 중 하나를 확인하고 번호를 식별하는 플래그를 설정할 수 있습니다 (편리하게 배열에서). 그리고 다음 단계에서 각 프로세스는 각 플래그를 확인하고 마지막으로 플래그가 지정되지 않은 번호를 출력 할 수 있습니다. 전체 과정은O(1)시간 이 걸립니다 . 추가O(n)공간 / 메모리 요구 사항이 있습니다.
참고 것을 주석에서 설명한 바와 같이 상기 제공된 두 개의 병렬 알고리즘의 추가 공간을 필요로 할 수있다 .
ArrayList 객체 (myList)가 해당 숫자로 채워져 있고 2 개의 숫자 x와 y가 누락되었다고 가정하면 가능한 솔루션은 다음과 같습니다.
int k = 1;
while (k < 100) {
if (!myList.contains(k)) {
System.out.println("Missing No:" + k);
}
k++;
}
가능한 해결책 :
public class MissingNumber {
public static void main(String[] args) {
// 0-20
int [] a = {1,4,3,6,7,9,8,11,10,12,15,18,14};
printMissingNumbers(a,20);
}
public static void printMissingNumbers(int [] a, int upperLimit){
int b [] = new int[upperLimit];
for(int i = 0; i < a.length; i++){
b[a[i]] = 1;
}
for(int k = 0; k < upperLimit; k++){
if(b[k] == 0)
System.out.println(k);
}
}
}
'Programing' 카테고리의 다른 글
| JavaScript 배열을 무작위 화 (셔플)하는 방법은 무엇입니까? (0) | 2020.09.27 |
|---|---|
| git 저장소에서 디렉토리를 제거하는 방법은 무엇입니까? (0) | 2020.09.27 |
| LF는 git에서 CRLF로 대체됩니다-그게 무엇이며 중요합니까? (0) | 2020.09.27 |
| 비동기 실행과 동기 실행, 이것이 실제로 무엇을 의미합니까? (0) | 2020.09.27 |
| PHP를 사용한“주의 : 정의되지 않은 변수”,“주의 : 정의되지 않은 인덱스”,“주의 : 정의되지 않은 오프셋” (0) | 2020.09.27 |