쉬운 인터뷰 질문이 어려워졌습니다: 1번이 주어졌습니다.100, 정확하게 k가 누락된 경우 결측 번호 찾기
저는 얼마 전에 재미있는 면접 경험을 했습니다.질문은 아주 쉽게 시작되었습니다.
Q1: 번호가 들어 있는 가방이 있습니다.
1,2,3, …,100각각의 숫자는 정확히 한 번 나타나므로 100개의 숫자가 있습니다.이제 가방에서 무작위로 하나의 번호가 선택됩니다.사라진 번호를 찾습니다.
물론 전에도 이 인터뷰 질문을 들은 적이 있기 때문에 다음과 같이 빠르게 대답했습니다.
A1: 음, 그 숫자들의 합.
1 + 2 + 3 + … + N이라(N+1)(N/2)(위키백과: 산술 급수의 합 참조).위해서N = 100이 합는입니다5050.따라서, 만약 모든 숫자가 가방 안에 있다면, 그 합은 정확하게 될 것입니다.
5050하나의 숫자가 빠졌기 때문에, 합은 이보다 적을 것이고, 차이는 그 숫자입니다. 그래서는우그리번찾수있을다습니호를된종실▁in▁number▁missing▁that▁so에서 빠진 숫자를 찾을 수 있습니다.O(N)과 간과시O(1)공간. 공간.
이 시점에서 저는 제가 잘했다고 생각했지만, 갑자기 질문이 예상치 못한 방향으로 바뀌었습니다.
Q2: 맞습니다. 하지만 이제 두 개의 숫자가 누락된 경우에는 어떻게 하시겠습니까?
저는 이런 변화를 전에 본 적이 없어서 당황해서 질문에 대답할 수 없었습니다.면접관이 나의 사고 과정을 알아야 한다고 주장했기 때문에, 나는 아마도 우리가 예상되는 제품과 비교하거나 첫 번째 패스에서 약간의 정보를 수집한 후에 두 번째 패스를 함으로써 더 많은 정보를 얻을 수 있을 것이라고 언급했습니다.하지만 저는 해결책에 대한 명확한 길을 찾기보다는 그저 어둠 속에서 촬영하고 있었습니다.
면접관은 두 번째 방정식을 갖는 것이 문제를 해결하는 한 가지 방법이라고 말하면서 저를 격려하려고 노력했습니다.이 시점에서 저는 (답을 미리 알지 못한 것에 대해) 약간 화가 났고, 이것이 일반적인 ("유용한") 프로그래밍 기술인지 아니면 그냥 속임수/얻은 답인지 물었습니다.
면접관의 대답은 저를 놀라게 했습니다: 당신은 3개의 누락된 숫자를 찾는 기술을 일반화할 수 있습니다.실제로, 당신은 그것을 일반화해서 k개의 결측번호를 찾을 수 있습니다.
QK: 가방에서 정확히 k개의 숫자가 빠진다면 어떻게 효율적으로 찾으시겠습니까?
이것은 몇 달 전의 일이고, 저는 여전히 이 기술이 무엇인지 알아낼 수 없었습니다.분명히 그것은.Ω(N)시간 하한은 우리가 모든 숫자를 적어도 한 번은 스캔해야 하기 때문에, 면접관은 해결 기술의 시간과 공간 복잡성을 주장했습니다.O(N)시간 입력 스캔)이 N이 아닌 N으로 정의됩니다.
여기서 질문은 간단합니다.
- Q2를 어떻게 해결하시겠습니까?
- Q3를 어떻게 해결하시겠습니까?
- Qk를 어떻게 풀겠습니까?
명확화
- 일반적으로 1부터 N개의 숫자가 있습니다.N, 하나만이 아닙니다.100.
- 나는 비트 세트를 사용하여 각 숫자의 존재/존재를 지정된 비트 값으로 인코딩하는 명백한 세트 기반 솔루션을 찾고 있지 않습니다. 따라서,
O(N)비트가 추가 공간에 있습니다.우리는 N에 비례하는 추가 공간을 마련할 수 없습니다. - 저는 또한 명백한 우선순위 접근법을 찾고 있지 않습니다.이와 세트 기반 접근 방식은 인터뷰에서 언급할 가치가 있습니다(실행하기 쉽고 N에 따라 매우 실용적일 수 있음).저는 성배 솔루션을 찾고 있습니다(실용적일 수도 있고 그렇지 않을 수도 있지만 그럼에도 불구하고 원하는 점근적 특성을 가지고 있습니다).
은 서물론입스합니다야해의 .O(N)그러나 N이 아닌 K 단위로 정의된 소량의 정보만 캡처할 수 있으며, K개의 결측 번호를 어떻게든 찾아야 합니다.
여기 Dimitris Andreou의 링크에 대한 요약이 있습니다.
i번째 거듭제곱의 합을 기억하세요. 여기서 i=1,2,...,k. 이것은 방정식 시스템을 푸는 문제를 줄입니다.
a1 + a2 + ...ak = b1
a12 + a22 + ...ak2 = b2
...
a1k + a2k + ...akk = bk
뉴턴의 정체성을 이용해서, 아는i 것이 계산을 가능하게 합니다.
c1 = a1 + a2 + ...a의k
c212 = aa13 + aa + ...aak-1k
...
ck12 = aa ...a의k
다항식(x-a1)...(x-ak)을 확장하면 계수가 정확히1 c, ..., c가k 됩니다. Viète의 공식을 참조하십시오.모든 다항식 요인(다항식의 고리가 유클리드 도메인임)은 a가 순열까지 고유하게 결정된다는 것을 의미합니다i.
이것은 힘을 기억하는 것이 숫자를 회복하기에 충분하다는 증거를 끝냅니다.상수 k의 경우 이 방법이 좋습니다.
그러나 k가 변화할 때 c,..., c를k 계산하는1 직접적인 접근법은 비용이 매우 많이 듭니다. 예를k 들어 c는 모든 누락된 숫자, 크기 n!/(n-k)!의 곱이기 때문입니다.이를 극복하려면 Z 필드에서 계산을q 수행합니다. 여기서 q는 n <= q < 2n - Bertrand의 가정에 의해 존재하는 소수입니다.공식은 여전히 유효하고 다항식의 인수분해는 여전히 고유하기 때문에 증명을 변경할 필요가 없습니다.또한 Berlekamp 또는 Cantor-Zassenhaus와 같이 유한 필드에 대한 인수 분해 알고리즘이 필요합니다.
상수 k에 대한 상위 수준 의사 코드:
- 주어진 숫자의 i번째 거듭제곱 계산
- 알 수 없는 숫자의 i번째 거듭제곱의 합을 구하려면 빼기.합계를i b라고 합니다.
- 뉴턴의 항등식을 사용하여 b에서i 계수를 계산합니다. c라고i 합니다.기본적으로1 c = b1; c2 = (cb11 - b2)/2; 정확한 공식은 위키백과를 참조하십시오.
- 다항식 x-cxk1k-1 + ... + c를k 요인화합니다.
- 다항식의 근은 필요한1 수 a, ..., a입니다k.
다양한 k에 대해, 예를 들어, prime n <= q < 2n을 구하시오.Miller-Rabin, 그리고 모든 숫자를 줄인 모듈로 단계를 수행합니다.
EDIT: 이 답변의 이전 버전에서는 q가 소수인 Z 대신q 특성 2의 유한 필드(q=2^(log n))를 사용할 수 있다고 명시했습니다.뉴턴의 공식은 k까지의 숫자로 나눗셈을 요구하기 때문에 그렇지 않습니다.
무투크리쉬난 - 데이터 스트림 알고리즘: 퍼즐 1: 누락된 번호 찾기의 두 페이지를 읽으면 찾을 수 있습니다.이것은 당신이 찾고 있는 일반화를 정확히 보여줍니다.아마도 이것이 당신의 면접관이 읽은 것이고 왜 그가 이러한 질문을 던졌는지일 것입니다.
또한 의사 코드도 포함된 sdcvvc의 직접적인 관련 답변을 참조하십시오(허허! 그런 까다로운 수학 공식을 읽을 필요가 없습니다:) (고마워요, 수고했어요!)
우리는 숫자 자체와 숫자의 제곱을 모두 합하여 Q2를 풀 수 있습니다.
그러면 문제를 줄일 수 있습니다.
k1 + k2 = x
k1^2 + k2^2 = y
에▁where디x그리고.y합계가 기대값보다 훨씬 낮은 값입니다.
대체 기능은 다음과 같습니다.
(x-k2)^2 + k2^2 = y
그리고 나서 우리가 우리의 잃어버린 숫자를 결정하기 위해 해결할 수 있습니다.
@j_random_hacker가 지적했듯이, 이것은 O(n) 시간 및 O(1) 공간에서 중복 항목 찾기와 매우 유사하며, 여기서도 제 답변의 적응이 작동합니다.
이 1개의 "방이"로 합니다.A[]가 크의인N - k우리는 Qkin을 풀 수 있습니다.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
번째 는 첫번루프다초기합니다화음을는째ises▁the다▁initial를 초기화합니다.k(한다는 것을 있는 편리한 값일 입니다. - 이 단계 된 항목이 표시됩니다.)N-k확장 배열에 여전히 없음).
가 " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " " "x한 번 이상 존재하면 해당 항목 중 하나가 위치합니다.A[x].
중첩된 루프가 있지만 다음 기간에 실행됩니다.O(N)- 은 시스 - ▁is▁an▁if다▁occurs▁time발▁only▁swap▁ai 식으로A[i] != i 각 은 적어도 합니다. 예를 , " " " " " " " " 입니다.A[i] == i전에는 그렇지 않았던 곳에서., 총수 " " " " " " " ( " " " ( " " " " " " "의 총 수)는 " " " 입니다.while body 루본는다최니대입입니다.N-1.
합니다.i가치에 의해 점유되지 않는.i이것은 이라는 것을 의미합니다.i실종된 게 틀림없어요
저는 4살짜리 아이에게 이 문제를 해결해 달라고 부탁했습니다.그는 숫자들을 분류하고 나서 따라 세었습니다.이것은 O(주방 바닥)의 공간이 요구되며, 공이 몇 개 없어도 쉽게 작동합니다.
가장 효율적인 솔루션인지는 모르겠지만, 모든 항목을 루프하고 비트셋을 사용하여 기억하고 어떤 숫자가 설정되어 있는지 기억한 다음 0비트를 테스트합니다.
저는 간단한 해결책을 좋아합니다. 그리고 저는 심지어 그것이 합이나 제곱합 등을 계산하는 것보다 빠를 수도 있다고 믿습니다.
수학을, 저는 가 수학아컴은확못만,는마도터퓨지.Σ(n^2)가 계산하는 으로.Σ(n) 두 개 누 락 번 호 얻 수 있 충 정 것 입 니 다 제 할 공 를 보 한 분 의 는 을 된 를 ▁info ▁to ▁would ▁missing ▁enough , ▁do ▁provide ▁numbers ▁get ▁two 다 니 것 입 제할 개Σ(n^3)세 개가 있는 경우에도 마찬가지입니다.
숫자의 합에 기반한 솔루션의 문제는 큰 지수를 가진 숫자를 저장하고 작업하는 비용을 고려하지 않는다는 것입니다.실제로, 매우 큰 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^jceil(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를 입력합니다.해스켈 구문에서...
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))이 알고리즘은 보다 직관적이고 시간 복잡성이 동일하며 공간을 적게 사용합니다.
Q2에 대한 매우 간단한 해결책은 아무도 대답하지 않은 것에 놀랐습니다.Q1의 방법을 사용하여 결측값 두 개의 합을 찾습니다.S로 표시하면 결측값 중 하나가 S/2보다 작고 다른 하나가 S/2(dh)보다 큽니다.1에서 S/2까지의 모든 숫자를 합한 다음 공식의 결과와 비교합니다(Q1의 방법과 유사). 결측된 숫자 사이의 작은 값을 찾습니다.더 큰 결측값을 찾으려면 S에서 뺍니다.
잠깐만.질문에 나와 있듯이, 가방 안에는 100개의 숫자가 들어 있습니다.k가 아무리 크더라도, 한 세트를 사용할 수 있고 최대 100k의 루프 반복으로 한 세트에서 숫자를 제거할 수 있기 때문에 문제는 일정한 시간 내에 해결될 수 있습니다.100은 상수입니다.나머지 숫자들의 집합이 당신의 답입니다.
1에서 N까지의 수에 대한 해를 일반화하면 N을 제외하고는 변화하는 것은 아무것도 상수가 아니므로 O(N - k) = O(N) 시간에 있습니다.예를 들어 비트 세트를 사용하면 O(N) 시간에 비트를 1로 설정하고 숫자를 반복한 다음 비트를 0으로 설정합니다(O(N-k) = O(N)). 그러면 답이 나옵니다.
면접관이 최종 세트 내용을 O(N) 시간이 아닌 O(k) 시간으로 출력하는 방법을 물어본 것 같습니다.분명히, 비트 세트를 사용하면 숫자를 인쇄할지 여부를 결정하기 위해 모든 N비트를 반복해야 합니다.그러나 세트가 구현되는 방식을 변경하면 숫자를 반복해서 출력할 수 있습니다.이 작업은 해시 집합과 이중으로 연결된 목록 모두에 저장할 개체에 숫자를 넣는 방식으로 수행됩니다.해시 집합에서 개체를 제거하면 목록에서도 개체를 제거할 수 있습니다.답변은 현재 길이가 k인 목록에 남아 있습니다.
2개(및 3개)의 결측 숫자 문제를 해결하기 위해, 평균적으로 실행되는 숫자를 수정할 수 있습니다.O(n)파티션을 인플레이스로 분할하는 경우에는 일정한 메모리를 사용합니다.
피벗에 합니다. 임 을 로 집 합
pl피보다작숫포함는경하우를자은벗▁smaller▁numbers경▁which우▁contain는▁and▁the를 포함합니다.r피벗보다 큰 숫자를 포함합니다.값을 하여 두 가 어떤 합니다("pivot ").
p - 1 - count(l) = count of missing numbers in l그리고.n - count(r) - p = count of missing numbers in r)각 파티션에 하나의 숫자가 없는 경우 합의 차이 접근법을 사용하여 각 숫자를 찾습니다.
(1 + 2 + ... + (p-1)) - sum(l) = missing #1그리고.((p+1) + (p+2) ... + n) - sum(r) = missing #2누락되어이 비어 는 한파티두개의숫모누있두락파고다비어니하누입나다중숫음자는락된있으면이티션어에되션자가▁either▁if▁are다▁then니하입,나▁is▁and입니다.
(p-1,p-2)또는(p+1,p+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);
}
}
2분기의 경우 다른 솔루션보다 다소 비효율적이지만 O(N) 런타임이 있고 O(k) 공간이 필요한 솔루션입니다.
이 아이디어는 원래 알고리즘을 두 번 실행하는 것입니다.첫 번째 숫자에서 누락된 총 숫자를 얻을 수 있습니다. 이것은 누락된 숫자의 상한을 제공합니다.이번호전화요해로▁this요전해화▁let▁call라고 부르자.N누락된 두 숫자는 총계가 될 것입니다.N따라서 첫 번째 숫자는 간격에만 있을 수 있습니다.[1, floor((N-1)/2)]두 번째가 있을 동안에[floor(N/2)+1,N-1].
따라서 첫 번째 구간에 포함되지 않은 모든 숫자를 삭제하고 모든 숫자를 다시 반복합니다.그것들은, 당신이 그들의 합계를 기록하는 것입니다.마지막으로, 당신은 빠진 두 개의 숫자 중 하나를 알게 될 것이고, 더 나아가서는 두 번째 숫자를 알게 될 것입니다.
이 방법이 일반화될 수 있고 입력을 한 번 통과하는 동안 여러 검색이 "병렬"로 실행될 수도 있다는 느낌이 들지만, 방법을 아직 파악하지 못했습니다.
여기에 kbit의 추가 스토리지를 사용하는 솔루션이 있습니다. 교묘한 속임수 없이 간단하게 말입니다.실행 시간 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; }
}
}
동기
일반적인 경우 문제를 해결하고 배열을 저장하고 편집할 수 있다면 Cafe의 솔루션이 가장 효율적입니다.어레이(스트리밍 버전)를 저장할 수 없는 경우 sdcvvc의 답변이 현재 제안된 유일한 솔루션 유형입니다.
제가 제안하는 솔루션은 배열을 저장할 수 있지만 편집할 수 없는 경우 가장 효율적인 답변(이 스레드에서 지금까지)이며, 누락된 항목 1~2개를 해결하는 스발로젠의 솔루션에서 아이디어를 얻었습니다.이 솔루션은 다음과 같습니다.Θ(k*n)과 간과시O(min(k,log(n)))그리고.Ω(log(k))공간입니다. 병렬 처리에도 잘 작동합니다.
개념.
은 만약 이 원래의 을 비교하는 한다면: 개 념 합 은 비 을 하 는 이 됩 같 니 다 다 이 과 음 면 사 하 용 을 식 방 접 래 의 근 원 교 됩 ▁the : 니 다 이 ▁of ▁sums ▁if ▁is ▁the ▁you▁that ▁idea 같
sum = SumOf(1,n) - SumOf(array)
그런 다음 결측값의 평균을 구합니다.
average = sum/n_missing_numbers
경계를 제공하는 것: 누락된 숫자 중 적어도 하나는 다음과 같거나 작은 숫자가 있어야 합니다.average 그리고 적어도 하나 이상의 숫자.average즉, 어레이를 각각 스캔하는 하위 문제로 나눌 수 있습니다 [O(n)
코드
C-style 솔루션(글로벌 변수에 대해 나를 판단하지 말고 C가 아닌 사람들이 읽을 수 있도록 코드를 만들려는 것입니다.):
#include "stdio.h"
// Example problem:
const int array [] = {0, 7, 3, 1, 5};
const int N = 8; // size of original array
const int array_size = 5;
int SumOneTo (int n)
{
return n*(n-1)/2; // non-inclusive
}
int MissingItems (const int begin, const int end, int & average)
{
// We consider only sub-array elements with values, v:
// begin <= v < end
// Initialise info about missing elements.
// First assume all are missing:
int n = end - begin;
int sum = SumOneTo(end) - SumOneTo(begin);
// Minus everything that we see (ie not missing):
for (int i = 0; i < array_size; ++i)
{
if ((begin <= array[i]) && (array[i] < end))
{
--n;
sum -= array[i];
}
}
// used by caller:
average = sum/n;
return n;
}
void Find (const int begin, const int end)
{
int average;
if (MissingItems(begin, end, average) == 1)
{
printf(" %d", average); // average(n) is same as n
return;
}
Find(begin, average + 1); // at least one missing here
Find(average + 1, end); // at least one here also
}
int main ()
{
printf("Missing items:");
Find(0, N);
printf("\n");
}
분석.
잠시 동안 재귀를 무시하면 각 함수 호출은 분명히 다음을 수행합니다.O(n)과 간과시O(1) 공백에 하세요. 참고:sum와 동등할 수 있습니다.n(n-1)/2 두 양 비 트 필 한 요 데 ▁so 니n-1이것은 어레이의 크기에 관계없이 효과적으로 두 개의 추가적인 요소 가치의 공간이 필요하다는 것을 의미합니다.k그러므로 그것은 여전히O(1)정상적인 관례 아래의 공간.
얼마나 많은 기능 호출이 있는지는 명확하지 않습니다.k누락된 요소가 있습니다. 영상을 제공하겠습니다. 배열 배열은 전체 " " " " " " " " " " " " " " " " " " " " " " " " " " " " 이 됩니다.k누락된 요소가 있습니다.우리는 그들을 점점 더 순서대로 상상할 것이다, 어디에서.--연결을 나타냅니다(같은 하위 어레이의 일부).
m1 -- m2 -- m3 -- m4 -- (...) -- mk-1 -- mk
의 Find기능은 누락된 요소를 서로 다른 겹치지 않는 하위 요소로 분리하는 것입니다.각 하위 어레이에 하나 이상의 누락된 요소가 있음을 보장하며, 이는 정확히 하나의 연결을 끊는 것을 의미합니다.
이것이 의미하는 것은 분열이 어떻게 발생하든, 그것은 항상 걸릴 것이라는 것입니다.k-1 Find함수는 누락된 요소가 하나만 있는 하위 요소를 찾는 작업을 수행합니다.
는 따서시간복잡은성라▁so은입니다.Θ((k-1 + k) * n) = Θ(k*n).
공간 복잡성의 경우, 매번 비례적으로 나누면 다음과 같습니다.O(log(k)) 복잡성, 만약 가 한 한다면, 은 우리에게 간 복 성 잡 만 우 한 가 리 번 하 하 에 나 분 만 면 다 줍 그 다 한 니 리 우 것 게 은 에 리 지 공 만 약 ▁us ▁space ▁complex ▁gives 다 ▁but 줍 , ▁one ▁if , 니 ▁we ity ▁separate 하O(k).
공간 복잡성이 다음과 같은 이유에 대한 증거를 보려면 여기를 참조하십시오.O(log(n))위에 언급한 것을 고려할 때, 우리는 그것이 또한O(k)그면우는그것이리라는 .O(min(k,log(n))).
이 알고리즘은 질문 1에 대해 작동할 수 있습니다.
- 사전 계산 x 또는 처음 100개 정수(val=1^2^3^4....100)
- x 또는 계속 입력 스트림에서 오는 요소(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
이제 밸브에서 a1과 a2를 체로 걸러내기 위해 밸브의 모든 세트 비트를 취합니다.예를 들어,ith비트가 val로 설정됩니다.즉, a1과 a2의 패리티는 다음과 같습니다.ith하고 두 값을 합니다.이제 원래 배열에 대해 다른 반복을 수행하고 두 개의 xor 값을 유지합니다.하나는 i번째 비트가 설정된 숫자이고 다른 하나는 i번째 비트가 설정되지 않은 숫자입니다.우리는 이제 두 양동이의 숫자를 가지고 있고, 그것은 확실합니다.a1 and a2다른 버킷에 있습니다.이제 각 버킷에서 하나의 누락된 요소를 찾았을 때와 동일한 작업을 반복합니다.
이와 같은 스트리밍 문제를 해결하는 일반적인 방법이 있습니다.그아디는확희 '산하로으 '기위'해약 '이의'간무 '화를'것사 '입니는'를 입니다.k요소를 독립적인 하위 문제로 전환하여 원래 알고리즘이 문제를 해결합니다.이 기술은 희소 신호 재구성 등에 사용됩니다.
- 배을만들고열,,
a가 크의인u = k^2. - 범용 해시 함수를 선택합니다.
h : {1,...,n} -> {1,...,u}(다중 시프트처럼) - 각에
i1, ..., 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은 @Andreou의 다항식이는 @Dimitris Andreou의 답변에 필요한 공간(특히 무작위화되는 다항식 인수 분해의 공간 요구 사항)과 일치합니다. 이 하지 않고 이 일정합니다.k정전의 경우.
사실, 우리는 댓글에 설명된 트릭을 사용하여 전력 합계 방법보다 훨씬 더 효율적일 수 있습니다.
모든 번호가 존재하는지 확인할 수 있습니까?예를 들어, 다음과 같이 시도할 수 있습니다.
S = 가방 안의 모든 숫자의 합 (S < 5050)
= - SZ = 결값 5050 - S의
가 누된숫있인 x그리고.y그러면:
- 및 x = Z - y 및
- 1max(x) = Z - 1
여러분은 를확다니합인에서 를 확인합니다.1max(x)그리고 번호를 찾습니다.
두 리스트의 합과 두 리스트의 곱이 있으면 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
그런 다음 2차 공식으로 해결할 수 있습니다.
b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b
샘플 파이썬 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, reduction 및 sum 함수의 복잡성을 모르기 때문에 이 솔루션의 복잡성을 해결할 수 없습니다(알고 있는 사람이 있다면 아래에 코멘트해 주십시오).
여기 sdcvc/Dimitris Andreou의 답변처럼 복잡한 수학에 의존하지 않고, 카페 및 Collonel Panic이 그랬던 것처럼 입력 배열을 변경하지 않으며, Chris Lercher, Jeremy P 및 많은 다른 사람들이 사용했던 것처럼 거대한 크기의 비트셋을 사용하지 않는 솔루션이 있습니다.기본적으로 저는 2분기에 대한 스발로젠/길라드 도이치의 아이디어로 시작하여 일반적인 사례 Qk로 일반화하고 알고리즘이 작동함을 증명하기 위해 자바로 구현했습니다.
그 생각
임의 구간 I이 있다고 가정하고, 이 구간에 결측된 숫자 중 적어도 하나만 포함되어 있다고 가정합니다.입력 배열을 통과한 후 I에서 나온 숫자만 보면 I에서 빠진 숫자의 합 S와 양 Q를 모두 얻을 수 있습니다.우리는 단순히 (Q를 얻기 위해) I에서 숫자를 만날 때마다 I의 길이를 줄이고 (S를 얻기 위해) I에서 모든 숫자의 사전 계산된 합을 매번 마주친 숫자로 줄임으로써 이를 수행합니다.
이제 S와 Q를 살펴보겠습니다.Q = 1이면 결측 숫자 중 하나만 포함하고 이 숫자는 분명히 S입니다.우리는 I를 완료된 것으로 표시하고(프로그램에서 "명백하지 않음"이라고 함) 추가 검토에서 제외합니다.반대로 Q > 1이면 I에 포함된 결측수의 평균 A = S / Q를 계산할 수 있습니다.모든 숫자가 다르므로 이러한 숫자 중 하나 이상은 A보다 엄격하게 작으며 하나 이상은 A보다 엄격하게 큽니다.이제 A의 I를 두 개의 작은 간격으로 나누는데, 각각은 적어도 하나의 결측 번호를 포함합니다.A가 정수일 경우 어느 구간에 A를 할당하는지는 중요하지 않습니다.
우리는 각각의 간격에 대해 S와 Q를 계산하는 다음 배열 통과를 개별적으로(그러나 동일한 경로로) 만든 다음, Q = 1로 간격을 표시하고 Q > 1로 간격을 분할합니다.우리는 새로운 "모호한" 구간이 없을 때까지 이 과정을 계속합니다. 즉, 각 구간에 정확히 하나의 결측 번호가 포함되어 있기 때문에 분할할 것이 없습니다(그리고 S를 알고 있기 때문에 항상 이 번호를 알고 있습니다).모든 가능한 숫자를 포함하는 유일한 "전체 범위" 간격에서 시작합니다(예: [1]).그 건에 있어서)
시간 및 공간 복잡도 분석
공정이 중지될 때까지 수행해야 하는 총 통과 p의 수는 결측값 카운트 k보다 크지 않습니다.부등식 p <= k는 엄격하게 증명될 수 있습니다.반면에 k의 큰 값에 유용한 경험적 상한 p < logN2 + 3도 있습니다.입력 배열이 속한 간격을 결정하려면 각 입력 배열 수에 대해 이진 검색을 수행해야 합니다.이렇게 하면 시간 복잡도에 로그 승수가 추가됩니다.
총 시간 복잡도는 O(N ᛫ min(k, 로그 N) ᛫ log k)입니다.큰 k의 경우, 이것은 sdcvvc/Dimitris Andreou의 방법인 O(N µk)보다 훨씬 낫습니다.
작업을 위해, 알고리즘은 최대 k 간격으로 저장하기 위해 O(k)의 추가 공간이 필요하며, 이는 "비트셋" 솔루션의 O(N)보다 훨씬 좋습니다.
자바 구현
위의 알고리즘을 구현하는 자바 클래스가 있습니다.항상 결측 번호의 정렬된 배열을 반환합니다.그 외에도 누락된 숫자는 1차 패스로 계산하기 때문에 카운트할 필요가 없습니다.숫자의 전체 범위는 다음과 같습니다.minNumber그리고.maxNumber매개 변수(예: 질문의 첫 번째 예에 대한 1 및 100).
public class MissingNumbers {
private static class Interval {
boolean ambiguous = true;
final int begin;
int quantity;
long sum;
Interval(int begin, int end) { // begin inclusive, end exclusive
this.begin = begin;
quantity = end - begin;
sum = quantity * ((long)end - 1 + begin) / 2;
}
void exclude(int x) {
quantity--;
sum -= x;
}
}
public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
Interval full = new Interval(minNumber, ++maxNumber);
for (inputBag.startOver(); inputBag.hasNext();)
full.exclude(inputBag.next());
int missingCount = full.quantity;
if (missingCount == 0)
return new int[0];
Interval[] intervals = new Interval[missingCount];
intervals[0] = full;
int[] dividers = new int[missingCount];
dividers[0] = minNumber;
int intervalCount = 1;
while (true) {
int oldCount = intervalCount;
for (int i = 0; i < oldCount; i++) {
Interval itv = intervals[i];
if (itv.ambiguous)
if (itv.quantity == 1) // number inside itv uniquely identified
itv.ambiguous = false;
else
intervalCount++; // itv will be split into two intervals
}
if (oldCount == intervalCount)
break;
int newIndex = intervalCount - 1;
int end = maxNumber;
for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
// newIndex always >= oldIndex
Interval itv = intervals[oldIndex];
int begin = itv.begin;
if (itv.ambiguous) {
// split interval itv
// use floorDiv instead of / because input numbers can be negative
int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
intervals[newIndex--] = new Interval(mean, end);
intervals[newIndex--] = new Interval(begin, mean);
} else
intervals[newIndex--] = itv;
end = begin;
}
for (int i = 0; i < intervalCount; i++)
dividers[i] = intervals[i].begin;
for (inputBag.startOver(); inputBag.hasNext();) {
int x = inputBag.next();
// find the interval to which x belongs
int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
if (i < 0)
i = -i - 2;
Interval itv = intervals[i];
if (itv.ambiguous)
itv.exclude(x);
}
}
assert intervalCount == missingCount;
for (int i = 0; i < intervalCount; i++)
dividers[i] = (int)intervals[i].sum;
return dividers;
}
}
공정성을, 이는 성을위해는, 의 형태로 .NumberBag물건들. NumberBag에서는 배열 수정 및 랜덤 액세스를 허용하지 않으며 순차적인 이동을 위해 배열이 요청된 횟수도 계산합니다.또한 대규모 어레이 테스트에 적합합니다.Iterable<Integer>원시의 복싱을 피하기 때문입니다.int큰 값을매큰고부감수있쌀다습니을분의 수 .int[]편리한 시험 준비를 위하여.원하는 경우 교체하는 것은 어렵지 않습니다.NumberBag타고int[]또는Iterable<Integer>을 타이프로 치다.find서명, 각 서명에 대한 두 개의 for-for-continue를 변경합니다.
import java.util.*;
public abstract class NumberBag {
private int passCount;
public void startOver() {
passCount++;
}
public final int getPassCount() {
return passCount;
}
public abstract boolean hasNext();
public abstract int next();
// A lightweight version of Iterable<Integer> to avoid boxing of int
public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
return new NumberBag() {
int index = toIndex;
public void startOver() {
super.startOver();
index = fromIndex;
}
public boolean hasNext() {
return index < toIndex;
}
public int next() {
if (index >= toIndex)
throw new NoSuchElementException();
return base[index++];
}
};
}
public static NumberBag fromArray(int[] base) {
return fromArray(base, 0, base.length);
}
public static NumberBag fromIterable(Iterable<Integer> base) {
return new NumberBag() {
Iterator<Integer> it;
public void startOver() {
super.startOver();
it = base.iterator();
}
public boolean hasNext() {
return it.hasNext();
}
public int next() {
return it.next();
}
};
}
}
테스트
이러한 클래스의 사용을 보여주는 간단한 예는 다음과 같습니다.
import java.util.*;
public class SimpleTest {
public static void main(String[] args) {
int[] input = { 7, 1, 4, 9, 6, 2 };
NumberBag bag = NumberBag.fromArray(input);
int[] output = MissingNumbers.find(1, 10, bag);
System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
Arrays.toString(input), Arrays.toString(output), bag.getPassCount());
List<Integer> inputList = new ArrayList<>();
for (int i = 0; i < 10; i++)
inputList.add(2 * i);
Collections.shuffle(inputList);
bag = NumberBag.fromIterable(inputList);
output = MissingNumbers.find(0, 19, bag);
System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
inputList, Arrays.toString(output), bag.getPassCount());
// Sieve of Eratosthenes
final int MAXN = 1_000;
List<Integer> nonPrimes = new ArrayList<>();
nonPrimes.add(1);
int[] primes;
int lastPrimeIndex = 0;
while (true) {
primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
int p = primes[lastPrimeIndex]; // guaranteed to be prime
int q = p;
for (int i = lastPrimeIndex++; i < primes.length; i++) {
q = primes[i]; // not necessarily prime
int pq = p * q;
if (pq > MAXN)
break;
nonPrimes.add(pq);
}
if (q == p)
break;
}
System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
primes.length, MAXN);
for (int i = 0; i < primes.length; i++)
System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
}
}
대규모 어레이 테스트는 다음과 같은 방법으로 수행할 수 있습니다.
import java.util.*;
public class BatchTest {
private static final Random rand = new Random();
public static int MIN_NUMBER = 1;
private final int minNumber = MIN_NUMBER;
private final int numberCount;
private final int[] numbers;
private int missingCount;
public long finderTime;
public BatchTest(int numberCount) {
this.numberCount = numberCount;
numbers = new int[numberCount];
for (int i = 0; i < numberCount; i++)
numbers[i] = minNumber + i;
}
private int passBound() {
int mBound = missingCount > 0 ? missingCount : 1;
int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
return Math.min(mBound, nBound);
}
private void error(String cause) {
throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
}
// returns the number of times the input array was traversed in this test
public int makeTest(int missingCount) {
this.missingCount = missingCount;
// numbers array is reused when numberCount stays the same,
// just Fisher–Yates shuffle it for each test
for (int i = numberCount - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
if (i != j) {
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}
}
final int bagSize = numberCount - missingCount;
NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
finderTime -= System.nanoTime();
int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
finderTime += System.nanoTime();
if (inputBag.getPassCount() > passBound())
error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
if (found.length != missingCount)
error("wrong result length");
int j = bagSize; // "missing" part beginning in numbers
Arrays.sort(numbers, bagSize, numberCount);
for (int i = 0; i < missingCount; i++)
if (found[i] != numbers[j++])
error("wrong result array, " + i + "-th element differs");
return inputBag.getPassCount();
}
public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
BatchTest t = new BatchTest(numberCount);
System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
int minPass = Integer.MAX_VALUE;
int passSum = 0;
int maxPass = 0;
t.finderTime = 0;
for (int j = 1; j <= repeats; j++) {
int pCount = t.makeTest(missingCount);
if (pCount < minPass)
minPass = pCount;
passSum += pCount;
if (pCount > maxPass)
maxPass = pCount;
}
System.out.format("║ %9d %9d ║ %2d %5.2f %2d ║ %11.3f ║%n", missingCount, numberCount, minPass,
(double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
}
}
public static void main(String[] args) {
System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
System.out.println("║ Number count ║ Passes ║ Average time ║");
System.out.println("║ missimg total ║ min avg max ║ per search (ms) ║");
long time = System.nanoTime();
strideCheck(100, 0, 100, 1, 20_000);
strideCheck(100_000, 2, 99_998, 1_282, 15);
MIN_NUMBER = -2_000_000_000;
strideCheck(300_000_000, 1, 10, 1, 1);
time = System.nanoTime() - time;
System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
}
}
저는 이것이 복잡한 수학적 방정식과 이론 없이도 가능하다고 생각합니다.다음은 O(2n) 시간 복잡성 솔루션에 대한 제안입니다.
입력 양식 가정:
가방 안의 숫자 = n
결측 번호의 = k
가방 안의 숫자들은 길이 n의 배열로 표현됩니다.
알고리즘에 대한 입력 배열 길이 = 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;
}
이 매우 흥미로운 질문에 감사드립니다.
당신이 이 문제를 해결할 수 있는 뉴턴의 작품을 상기시켜 주었기 때문입니다.
뉴턴의 신원을 참조하십시오.
= 방정식 수를 찾을 변수 수(일관성을 위해 필요)
저는 이를 위해 백 수에 대한 검정력을 높여 다양한 방정식을 만들어야 한다고 생각합니다.
잘은 모르겠지만, 만약 기능이 있어야 한다면, 나는 믿습니다.f여기에i f(x)를 추가합니다.
x1 + x2 + ...xk = z1
x12 + x22 + ...xk2 = z2
............
............
............
x1k + x2k + ...xkk = zk
휴식은 시간과 공간의 복잡성에 대해 확신할 수 없는 수학적인 작업이지만 뉴턴의 정체성은 확실히 중요한 역할을 할 것입니다.
- 을 사용하면 안 되나요?
.difference_update()아니면 이 질문 방법에 선형 대수학의 가능성이 있습니까?
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) 공간에 얼마나 들어맞으며, 필요한 크기의 숫자를 합산하는 데 얼마나 걸립니까?
저는 30개의 답을 모두 읽었고 가장 간단한 답을 찾았습니다. 즉, 100개의 비트 배열을 사용하면 가장 좋습니다.그러나 질문에서 N 크기의 배열을 사용할 수 없다고 했듯이, 저는 O(1) 공간 복잡성과 키팅(kitation) 시간 복잡성을 사용하여 이를 해결할 것입니다.
설명을 더 쉽게 하기 위해, 제가 1부터 15까지의 숫자를 받았고 그 중 두 개, 즉 9와 14가 누락되었다고 생각합니다.가방을 다음과 같이 만듭니다.
[8,1,2,12,4,7,5,10,11,13,15,3,6].
우리는 각 숫자가 내부적으로 비트의 형태로 표현된다는 것을 알고 있습니다.16까지의 숫자는 4비트만 있으면 됩니다.10^9까지의 숫자는 32비트가 필요합니다.하지만 4비트에 초점을 맞추고 나중에 일반화할 수 있습니다.
이제 1부터 15까지의 모든 숫자가 있으면 내부적으로 다음과 같은 숫자가 있다고 가정합니다(주문한 경우).
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
하지만 지금 우리는 두 개의 숫자가 빠졌습니다.따라서 우리의 표현은 다음과 같습니다(이해를 위해 정렬된 것으로 표시되지만 어떤 순서로도 가능).
(2MSD|2LSD)
00|01
00|10
00|11
-----
01|00
01|01
01|10
01|11
-----
10|00
missing=(10|01)
10|10
10|11
-----
11|00
11|01
missing=(11|10)
11|11
이제 크기 2의 비트 배열을 만들어서 가장 중요한 두 자리 숫자의 수를 저장해 보겠습니다.예
= [__,__,__,__]
00,01,10,11
왼쪽과 오른쪽에서 백을 스캔하고 비트 배열의 각 빈에 숫자 수가 포함되도록 위 배열을 채웁니다.결과는 다음과 같습니다.
= [ 3, 4, 3, 3]
00,01,10,11
만약 모든 숫자가 있었다면, 다음과 같이 되었을 것입니다.
= [ 3, 4, 4, 4]
00,01,10,11
따라서 최대 2자리 숫자가 10인 숫자와 최대 2비트가 11인 숫자 두 개가 누락된 숫자가 있음을 알 수 있습니다.이제 목록을 다시 스캔하고 하위 2자리 유효 숫자에 대해 크기 2의 비트 배열을 작성합니다.이번에는 최대 2자리 숫자가 10인 요소만 고려합니다.비트 배열은 다음과 같습니다.
= [ 1, 0, 1, 1]
00,01,10,11
MSD=10의 모든 숫자가 존재한다면, 우리는 모든 빈에 1개가 있을 것이지만, 지금 우리는 하나가 누락된 것을 확인합니다.따라서 MSD=10 및 LSD=01이 누락된 번호는 1001, 즉 9입니다.
마찬가지로 다시 스캔하지만 MSD=11을 가진 요소만 고려하면 MSD=11 및 LSD=10이 누락됩니다. 즉, 1110은 14입니다.
= [ 1, 0, 1, 1]
00,01,10,11
따라서, 우리는 일정한 양의 공간에서 누락된 숫자를 찾을 수 있습니다.우리는 이것을 100, 1000, 10^9 또는 임의의 숫자 집합에 대해 일반화할 수 있습니다.
참고 자료: http://users.ece.utexas.edu/ 의 문제 1.6 ~adnan/afi-filename-new.pdf
아주 좋은 문제입니다.저는 Qk에 대해 설정된 차이를 사용하는 것에 찬성합니다.Ruby와 같은 많은 프로그래밍 언어도 지원합니다.
missing = (1..100).to_a - bag
가장 효율적인 솔루션은 아닐 수 있지만, 이 경우(알려진 경계, 낮은 경계)에 해당하는 작업에 직면할 경우 실생활에서 사용할 수 있는 솔루션입니다.숫자 집합이 매우 클 경우에는 물론 더 효율적인 알고리즘을 고려하겠지만, 그때까지는 간단한 해결책으로 충분할 것입니다.
블룸 필터를 사용해 볼 수 있습니다.가방에 있는 각 번호를 블룸에 삽입한 다음, 각 번호를 찾을 수 없을 때까지 전체 1k 세트에 걸쳐 반복합니다.이것이 모든 시나리오에서 답을 찾을 수는 없지만 충분히 좋은 해결책일 수 있습니다.
저는 그 질문에 대해 다른 접근법을 사용하여 면접관이 해결하려는 더 큰 문제에 대한 자세한 내용을 조사할 것입니다.문제와 이를 둘러싼 요구 사항에 따라 명확한 세트 기반 솔루션이 올바른 솔루션일 수 있으며, 나중에 선택하여 선택하는 방식은 그렇지 않을 수 있습니다.
예를 들어, 면접관이 파견을 갈 것입니다.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))등, 한 번의 패스로 계산할 수 있습니다.
어레이에서 어떤 항목이 누락되었는지 어떻게 알 수 있습니까? 다식에대생보세요해각해항▁the▁polynom에 대해 .(z-x_1)(z-x_2)...(z-x_n)은 라고평니다됩으로 됩니다.0만약 당신이 숫자 중 하나라도 입력한다면.x_i다항식을 확장하면 다음과 같이 됩니다.z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n기본 대칭 함수도 여기에 나타나는데, 우리가 어떤 순열을 뿌리에 적용하더라도 다항식은 동일하게 유지되어야 하기 때문에 놀라운 일은 아닙니다.
그래서 우리는 다항식을 만들고 다른 사람들이 언급한 것처럼 어떤 숫자가 집합에 있지 않은지 알아내기 위해 그것을 인수분해할 수 있습니다.
마지막으로, 만약 우리가 큰 숫자들로 넘쳐나는 메모리에 대해 걱정한다면 (그 다음 대칭 다항식은 순서가 될 것입니다.)100!), 을 할 수mod pp 100100 보다 큰 입니다.이 우리는 합니다.mod p그리고 그것이 다시 평가된다는 것을 발견합니다.0입력이 집합에 있는 숫자일 때, 입력이 집합에 없는 숫자일 때 0이 아닌 값으로 평가됩니다.그러나, 다른 사람들이 지적했듯이, 다음에 의존하는 시간 내에 다항식의 값을 얻기 위해.k,것은 아니다.N우리는 다항식을 인수해야 합니다.mod p.
나는 내가 가지고 있다고 믿습니다.O(k)과 간과시O(log(k))공간 알고리즘, 당신이 가지고 있다는 것을 고려할 때.floor(x)그리고.log2(x)사용 가능한 임의의 큰 정수에 대한 함수:
당신은 가지고 있습니다.k 정수bit long ▁the,log8(k)space할 때 합니다.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;
}
의 floor 이 없습니다.2756-비트 정수 대신 더블을 사용합니다.각 1,에 대해 숫자를 수 , 그서가 됩니까? 간단하게, 각 2바이트(또는 1, 3, 4)에 대해, 당신은 이 함수들을 사용하여 원하는 숫자를 얻을 수 있지만, 이것은 다음과 같은 추가를 합니다.O(N) 대
1에서 50 사이의 숫자의 곱을 찾으려고 합니다.
제품 P1 = 1 x 2 x 3 x ........... 50개
숫자를 하나씩 뺄 때 곱하면 P2가 나옵니다.그러나 여기서 두 개의 숫자가 누락되었으므로 P2 < P1.
a x b = P1 - P2라는 두 결측 항의 곱입니다.
a + b = S1의 합계를 이미 알고 있습니다.
위의 두 방정식에서 2차 방정식을 통해 a와 b를 풀어보세요. a와 b는 당신의 빠진 숫자입니다.
언급URL : https://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe
'sourcetip' 카테고리의 다른 글
| 판다와 함께 세포를 훌륭하게 색칠하기 (0) | 2023.05.23 |
|---|---|
| 이미지 URL을 system.drawing.image로 변환하려면 어떻게 해야 합니까? (0) | 2023.05.23 |
| python에서 목록이 항목을 공유하는지 테스트합니다. (0) | 2023.05.23 |
| ElementName 바인딩에 실패했습니다. (0) | 2023.05.23 |
| 목록(String) 또는 배열 또는 배열 목록 (0) | 2023.05.23 |