Kth Largest Element in a Stream

Q: k번째로 큰 요소에 최대 힙이 아닌 최소 힙을 사용하는 이유는 무엇인가요?

k 개의 가장 큰 값 중 가장 작은 값이 정답이자 새로 들어온 값이 넘어야 하는 값이며, 크기가 k 인 최소 힙은 이 값을 맨 위에 유지합니다. 모든 값을 담은 최대 힙은 가장 큰 값을 맨 위에 두므로, k 번째 값에 도달하려면 값이 들어올 때마다 k-1 개의 값을 꺼냈다가 다시 넣어야 합니다.

Q: 스트림에서 K번째로 큰 원소의 시간 복잡도는 무엇인가요?

각 요소가 도착할 때마다 O(log k) 의 비용이 듭니다. 맨 위 요소와 한 번 비교하고, k 개의 값으로 이루어진 힙을 최대 한 번 내려가며 정렬하기 때문입니다. nums 로 힙을 만드는 데는 O(n log k) 의 비용이 들므로, 전체 실행에는 O((n + m) log k) 의 시간과 O(k) 의 추가 공간이 필요합니다.

Q: 스트림에서 K번째로 큰 원소를 정렬된 목록으로 구할 수 있을까요?

네. 모든 값을 정렬된 상태로 유지하고, 이진 검색을 사용해 각 도착 값을 제자리에 삽입한 다음, 끝에서 k 번째 위치의 값을 읽습니다. 검색은 O(log n) 이지만, 삽입 위치 뒤의 값을 이동하는 작업은 도착할 때마다 O(n) 입니다. 시작 값 10^4 개와 도착 값 10^4 개가 있다면 약 1.5 × 10^8 번 이동하게 됩니다.

쉬움힙

+10

정수 스트림은 nums의 값으로 시작합니다. 그런 다음 adds의 값이 한 번에 하나씩 들어옵니다. 값이 들어올 때마다 지금까지 확인한 모든 값 중 k번째로 큰 값을 기록합니다. 같은 값도 각각 따로 셉니다. 기록한 값을 순서대로 반환하되, adds의 각 값에 대해 하나씩 반환합니다.

nums에는 최소 k-1개의 값이 있으므로, 첫 번째 값이 들어온 후에는 항상 선택할 값이 최소 k개 있습니다.

함수

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: 보고할 순위, 가장 큰 값은 1
numsinteger-array: 스트림에 이미 있는 값
addsinteger-array: 도착하는 값의 순서대로
반환값integer-array: 각 항목이 도착한 후 k번째로 큰 값

제약 조건

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums는 어떤 순서로든 있을 수 있으며, 같은 값도 별개의 값으로 계산됩니다.

예제

입력: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
출력: [3, 5, 6, 6, 7]
설명: 3 다음에는 7, 5, 3, 1 중 세 번째로 큰 수인 3이 옵니다. 그런 다음 9가 이를 5로 올리고, 6이 6으로 올리며, 2는 아무 변화도 주지 않고, 8이 7로 올립니다(9, 8, 7).

입력: k = 1nums = [-2]adds = [-5, 0, -1, 4]
출력: [-2, 0, 0, 4]
설명: k = 1일 때 답은 지금까지의 최댓값입니다. 0이 나올 때까지는 -2이고, -1 이후에도 여전히 0이며, 그다음은 4입니다.

후속 질문

값을 스트림에서 제거할 수도 있다면 같은 질문에 어떻게 답하시겠습니까?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

값은 스트림에서 절대 빠져나가지 않으므로, 현재 k번째로 큰 값보다 작은 값은 영원히 제외됩니다. 최소 힙에는 가장 큰 값 k개만 유지합니다. 힙의 맨 위가 답이며, 값이 하나 들어올 때마다 비교 한 번과 최대 한 번의 O(log k) 힙 갱신이 필요합니다.

도착할 때마다 정렬

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

모든 값을 목록에 보관합니다. 값이 추가될 때마다 오름차순으로 정렬하고, 정의에 따라 k번째로 큰 값인 인덱스 length-k를 읽습니다.

값이 추가될 때마다 최대 n + m개의 값을 정렬합니다. 여기서 n과 m은 각각 nums와 adds의 길이입니다. 각 길이가 10^4이면 총 비교 횟수는 약 2 × 10^9회입니다.

알고리즘

nums를 values 목록에 복사합니다.
adds의 각 값을 values에 추가합니다.
values를 오름차순으로 정렬하고 values[length-k]를 기록합니다.
기록한 값을 반환합니다.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

k개의 가장 큰 값으로 구성된 최소 힙

핵심 아이디어

어떤 값보다 큰 값이 k개 있으면, 스트림의 나머지 부분에서도 계속 그러므로 지금까지 본 값 중 가장 큰 k개만 중요합니다. 이 값들을 최소 힙에 저장합니다. 힙의 최상단은 가장 큰 k개 중 가장 작은 값이며, 전체에서 정확히 k번째로 큰 값입니다.

x가 도착했을 때 힙이 가득 차 있다면, x와 최상단을 비교합니다. x가 더 크지 않으면 가장 큰 k개에 속하지 않으므로 아무것도 바뀌지 않습니다. 더 크다면 최상단 값은 제외됩니다. 최상단 값을 x로 바꾸고 O(log k) 시간에 아래로 sift down 합니다. 시작 값에도 같은 절차를 적용하므로 nums는 k보다 길 수 있습니다.

첫 번째 예제에서 nums를 처리한 후 힙에는 7, 1, 5가 들어 있고, 최상단에는 1이 있습니다. 3이 도착하면 1을 대체하고, 최상단 값인 3이 첫 번째 답이 됩니다.

알고리즘

빈 최소 힙으로 시작합니다.
x를 추가하려면: 힙에 k개보다 적은 값이 들어 있으면 x를 푸시합니다. 그렇지 않으면 x가 최솟값보다 클 때 최솟값을 x로 바꾸고 힙의 순서를 복원합니다.
이 방법으로 nums의 모든 값을 추가합니다.
adds의 각 값을 추가하고 힙의 최솟값을 기록합니다.
기록한 값들을 반환합니다.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

함정과 경계 사례

중복 제거하기. 9, 6, 6, 6, 2 중 가장 큰 네 값은 9, 6, 6, 6입니다. 집합을 사용하거나 이미 있는 값을 건너뛰도록 검사하면 세 번째 예시에서 6 대신 2를 반환합니다.
추가하기 전에 답 읽기. nums에 k-1개의 값이 들어 있을 때 힙은 첫 번째 값이 들어온 후에야 가득 차므로, 먼저 추가한 다음 맨 위 값을 읽으세요.
정렬 후 잘못된 쪽부터 세기. 오름차순에서는 k번째로 큰 값이 인덱스 length-k에 있습니다. 인덱스 k-1에는 k번째로 작은 값이 있습니다.
기본 힙 순서를 그대로 사용하기. C++의 priority_queue와 Rust의 BinaryHeap은 최대 힙입니다. greater<int>를 전달하거나 값을 Reverse로 감싸세요.

자주 묻는 질문3

k번째로 큰 요소에 최대 힙이 아닌 최소 힙을 사용하는 이유는 무엇인가요?

k개의 가장 큰 값 중 가장 작은 값이 정답이자 새로 들어온 값이 넘어야 하는 값이며, 크기가 k인 최소 힙은 이 값을 맨 위에 유지합니다. 모든 값을 담은 최대 힙은 가장 큰 값을 맨 위에 두므로, k번째 값에 도달하려면 값이 들어올 때마다 k-1개의 값을 꺼냈다가 다시 넣어야 합니다.

스트림에서 K번째로 큰 원소의 시간 복잡도는 무엇인가요?

각 요소가 도착할 때마다 O(log k)의 비용이 듭니다. 맨 위 요소와 한 번 비교하고, k개의 값으로 이루어진 힙을 최대 한 번 내려가며 정렬하기 때문입니다. nums로 힙을 만드는 데는 O(n log k)의 비용이 들므로, 전체 실행에는 O((n + m) log k)의 시간과 O(k)의 추가 공간이 필요합니다.

스트림에서 K번째로 큰 원소를 정렬된 목록으로 구할 수 있을까요?

네. 모든 값을 정렬된 상태로 유지하고, 이진 검색을 사용해 각 도착 값을 제자리에 삽입한 다음, 끝에서 k번째 위치의 값을 읽습니다. 검색은 O(log n)이지만, 삽입 위치 뒤의 값을 이동하는 작업은 도착할 때마다 O(n)입니다. 시작 값 10^4개와 도착 값 10^4개가 있다면 약 1.5 × 10^8번 이동하게 됩니다.

def kthLargestStream(k, nums, adds):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

예상 출력

[3, 5, 6, 6, 7]