두 개의 가방에서 일치하는 것을 찾습니다.

Question

이것은 인터뷰 질문 중 하나였습니다. 제가 제대로했는지 궁금 해서요. 내 솔루션이 가장 효율적인 지 알고 싶습니다. O (N 로그 n)이

견과류의 가방과 볼트의 가방을 감안할 때, 각각은 다른 가방에서 크기 만 다른 가방에 정확히 하나의 일치는 모든 일치를 찾을 수있는 빠른 알고리즘을 제공합니다.

항상 2 봉지 사이에 일치하므로 너트의 수가 같고 볼트 수가 같을 것이라고 말했습니다. 숫자를 n으로합시다.

먼저 각 구성 요소의 무게를 각 구성 요소의 무게로 정렬하고, 모두 가방 내에서 크기가 다르기 때문에 가능합니다. 병합 정렬을 사용하면 O (n log n) 시간 복잡성을 갖게됩니다.

다음으로 가장 가벼운 부분부터 가장 무거운 부분까지 2 개 봉지의 각 구성 요소를 일치시키는 것은 간단합니다.

이것이 올바른 해결책인지, 그리고이 문제를 해결하는 다른 흥미로운 방법이 있는지 알고 싶습니다.

Answer 1

표준 해결책은 견과류의 가방을 해시 (또는 HashMap 또는 사전, 또는 선택한 언어가 무엇이든간에)에 넣은 다음 해시 조회를 사용하여 다른 가방을 걸어서 찾으십시오.

이 알고리즘의 평균 성능은 O(n)이며, 정렬/2 진 검색 변형보다 우수한 상수를 사용합니다.

Answer 2

저에게 가장 좋은 해결책 인 복잡성에 비춰 보입니다.

대안은 하나의 가방 만 정렬 한 다음 이진 검색을 사용하여 볼트와 너트를 일치시키는 것입니다 (정렬 된 목록에서 쌍을 제거하는 것). 여전히 O(n log n)이지만 두 번째 부분은 최적화 후 약간의 차이가 있습니다. 최악의 경우는 다음과 같습니다. log n + log n-1 + log n-2 ... 1 = (n log n)/2

Answer 3

정확한 크기를 측정하지 못했을 때만 볼 수 있습니다. 너무 크거나, 너무 작거나, 정확하게 시도하면, 이것은 정렬하는 방법에 대한 추가 단계를 필요로합니다. 아마도 임의의 너트를 취하고, 각 볼트와 비교하여 더 작은, 더 큰 더미로 정렬 한 다음, 볼트 그리고 그걸로 견과를 정렬 (수정 된 quicksort ... 당신은 너트 또는 볼트를 선택하는 방법의 문제를 다루어야 할 때 더미가 작아지면 비교하여 당신이 사용하고 있는지 확인하십시오 합리적인 피벗).

너트와 볼트에 크기가 표시되어 있거나 너트와 볼트의 크기를 측정 할 수있는 방법이 있다는 것을 알려주지 않으므로 해시 테이블을 사용하여이를 해결하는 것이 어려울 수 있습니다. 또는 심지어 정기적 인 비교 정렬.

Answer 4

두 개의 너트 또는 두 개의 볼트를 직접 비교할 수없는 경우에도 작동하는 O (nlgn)에서이 문제에 대한 해결책이 있습니다. 그것은 규모를 사용하지 않거나 무게의 차이가 너무 작아 관찰 할 수없는 경우입니다.

1. 가 임의의 볼트 B를 선택 : 그것은 다음과 같이 무작위 퀵의 작은 변화를 적용하여 작동

   .

2. 너트를 b보다 작고 b보다 큰 너트로 분할하여 볼트 b를 모든 너트와 비교하십시오.
3. 이제 볼트를 두 개의 반쪽으로 분할해야하며 볼트와 볼트를 비교할 수 없습니다. 그러나 이제 우리는 b와 일치하는 너트 n이 무엇인지 압니다. 그래서 우리는 n을 모든 볼트와 비교하여 크기가 n보다 작고 n보다 큰 볼트로 분할합니다.
4. 나머지 문제는 동일한 단계를 너트와 볼트의 더 적은 파티션과 더 큰 파티션에 적용하여 무작위 추출 바로 가기를 따릅니다.

Answer 5

2 봉지를 추가로 가져옵니다. 왼쪽 가방과 오른쪽 가방을 말해봐. 이제 각각의 너트를 잡고 각 볼트와 비교하십시오. 볼트가 작 으면 왼쪽 가방에 넣고, 오른쪽 가방에 넣으십시오. 이제 다음 너트를 가져 와서 이전에 찍은 너트와 비교해보십시오. 작 으면 왼쪽 가방의 너트 만 확인해야하며 그렇지 않은 경우 오른쪽 가방의 너트 만 확인해야합니다. 이 방식으로 계속하십시오.