Tencent에는 다음과 같은 학교 모집 질문이 있습니다.
메모리가 2G만 있는 PC의 경우 10G의 정수가 포함된 파일에서 중앙값을 찾아 알고리즘을 작성하세요.
버킷 정렬, 기수 정렬 등 여러 솔루션이 있지만 이를 해결하기 위해 힙을 사용하는 방법을 찾았습니다. 원래 단어는 다음과 같습니다.
먼저 찾아보세요. 1G maximum, 그런 다음 이 요소를 사용하여 2G maximum을 찾은 다음 2G maximum을 사용하여 3G maximum을 찾습니다. 물론 정렬할 필요는 없지만 디스크 작업이 더 많아집니다. 외부 정렬보다 효율적인 디스크 IO 분석이 필요합니다.
1g 정수의 최대값 힙을 생성합니다. 이 방법으로 힙에 넣습니다. 1g의 가장 큰 요소를 얻은 다음 이 요소를 사용하여 힙을 다시 재구축할 수 있습니다. 이번에는 힙에 들어가기 위한 조건 또한 이보다 더 큰 1g번째로 큰 요소를 추가해야 힙을 빌드한 후 다음을 얻을 수 있습니다. 2g번째로 큰 요소입니다.
처음에 1G가 무엇인지 이해가 안 됐어요. 10G 데이터를 10개로 나눈 다음, 1G 데이터를 정렬해서 가장 큰 의미를 찾는 건가요?
이 솔루션에 대해 조언을 주실 수 있기를 바랍니다. 감사합니다.
PHPz2017-05-16 13:03:22
힙은 완전한 이진 트리인 데이터 구조입니다(따라서 구조를 저장하는 데 포인터가 필요하지 않습니다). 각 노드는 큰 상단 힙과 작은 상단 힙에 해당하는 하위 노드보다 크거나 작지 않습니다. 각기. 예를 들어, 작은 최상위 힙에서는 루트 요소가 가장 작습니다. 따라서 O(1)的复杂度查找其中的最大或是最小的元素。其删除和插入元素的复杂度，最坏情况下都是O(log(N))로 사용할 수 있습니다.
이 구절은 먼저 (1G+1) 데이터를 수용할 수 있는 작은 상위 힙을 생성하면 그 안의 가장 작은 요소를 빠르게 찾을 수 있음을 의미합니다. 그런 다음 10G의 데이터를 모두 탐색하여 삽입합니다. 삽입 후 힙이 가득 찬 경우(힙에 1G+1 데이터가 있음) 가장 작은 것을 삭제하면 됩니다. . . .
최종 결과는 힙에 있는 데이터가 가장 큰 1G 데이터이고, 힙의 맨 위가 가장 작은 데이터라는 것입니다. 즉, 내림차순으로 정렬하면 이 데이터의 위치는 1G 위치입니다. 예를 들어, 이 숫자는 x입니다.
그런 다음 다시 위 과정을 계속 진행하는데 차이점은 x보다 작은 요소만 힙에 삽입되고 x보다 크거나 같은 요소는 무시된다는 점입니다. 즉, 방금 찾은 1G 데이터를 무시한 후 가장 큰 1G를 찾는다. 이런 식으로 최종 힙의 최상위는 정렬 후 2G 위치의 데이터가 됩니다. (단, 중복된 데이터를 다룰 때는 주의하세요.) . . . 그리고 계속해서 중앙값을 찾습니다.
漂亮男人2017-05-16 13:03:22
궁금한게 있는데 비트맵으로는 이런 질문을 할 수 없나요? . .
1. 이 10G 숫자를 탐색하고, 비트맵에 어떤 숫자가 나타났는지 표시하고, 얼마나 많은 다른 숫자가 나타났는지 계산하고, 이를 count로 기록합니다. 2. 비트맵을 탐색하고, 이 숫자인 개수/2번째 비트를 찾습니다. . .
ringa_lee2017-05-16 13:03:22
이 방법에 대해 여전히 몇 가지 다양한 질문이 있습니다. 마스터가 흥미를 느낀다면 다음을 살펴보세요.
10개의 힙으로 나누어져 있으므로 각 힙의 공통 경계 값은 무엇입니까?
10개의 더미로 나눈다면 최악의 경우 퀵 정렬에는 몇 번의 판단이 필요한가요?
계산량을 줄일 수 있나요?
@zonxin