[Leetcode] 703. Kth Largest Element in a Stream

문제 : https://leetcode.com/problems/kth-largest-element-in-a-stream/

---

k, nums 배열을 초기값으로 입력받고, 정수값 val을 nums 배열에 추가하는 함수 add를 제공할 때,

k번째로 큰 원소를 찾기위한 클래스를 설계해라.

---

최대힙, 최소힙을 만들고 최소 힙의 크기는 k로 유지시킨다.

최소힙에는 k개의 큰 수들이 들어갈 것이고 이외의 수들은 모두 최대힙에 넣는다.

 

nums = [1,2,7,4,3], k = 2 로 예를 들어보자.

초기값

[1, 2]

1, 2 원소는 min heap에 용량이 아직 남았으므로 모두 min heap 에 넣어준다.

[7]

3번째 원소 7을 넣을때는 min heap이 모두 찼으므로 min heap의 top에 있는 수와 7을 비교한다.

min heap의 top에 있는 1보다 7이 더 크므로 더 작은 수인 1은 max heap으로 옮기고 7을 min heap에 넣어준다.

[4]

4도 7과 마찬가지의 이유로 원소 2는 최대힙으로 옮기고 4는 최소힙에 넣어준다.

[3]

추가하고자 하는 수 3은 최소힙의 top에 있는 4보다 작기 때문에 최소힙의 변경없이 3을 최대힙에 넣어준다.

[완성]

값 세팅이 끝나고 최소힙의 top에 있는 수가 k번째로 큰수가 된다.

 

add 함수의 시간복잡도는 O(logk)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/703.%20Kth%20Largest%20Element%20in%20a%20Stream.cpp

---

사실 최대힙을 만들긴 했지만 num 배열에 추가만 하기 때문에 최대힙은 필요없다. ㅎㅎ.. 자료 다 만들고 나서 깨달아서 그냥 같이 설명했다.

비슷한 문제 : [295] Find Median from Data Stream