[알고리즘] LeetCode 703번 "Kth Largest Element in a Stream" (C/C++) - Don 임베디드

문제요약:

Implement KthLargest class that finds the Kth largest element in a stream.

1. Constructor KthLargest(int k, int [] nums)

Initialize the object with K value and stream of integers nums.

2. int add(int val)

Appends the integer val to the stream and returns the Kth largest element

 

 

제약:

1 <= k <= 10^4

0 <= nums.length <= 10^4

-10^4 <= nums[i] <= 10^4

-10^4 <= val <= 10^4

at most 10^4 calls will be made to add function.

It is guaranteed that there will be at least K elements will be in the array when searching for Kth element.

 

예제 1 입력.	예제 1 출력.
["KthLargest", "add", "add", "add", "add", "add"] [[3, [4,5,8,2]], [3], [5], [10], [9], [4]]	[null,4,5,5,8,8]
예제 2 입력.	예제 2 출력.
["KthLargest", "add", "add", "add", "add", "add"] [[1,[]],[-3],[-2],[-4],[0],[4]]	[null,-3,-2,-2,0,4]

 

정답코드 I: Binary Search

class KthLargest {
public:
    vector <int> V;
    int nKth;
    
    KthLargest(int k, vector<int>& nums) {
        nKth = k;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++)
        {
            V.push_back(nums[i]);
        }
    }
    
    int add(int val) {
        int nStart = 0;
        int nEnd = V.size() - 1;
        int nMid = 0;
        
        if (V.size() == 0)
        {
            V.push_back(val);
            return V[V.size()-nKth];
        }
        
        while (nStart < nEnd)
        {
            nMid = (nStart + nEnd) / 2;
            
            if (V[nMid] == val)
            {
                break;
            }
            else if (V[nMid] < val)
            {
                nStart = nMid + 1;
                nMid = (nStart + nEnd) / 2;
            }
            else
            {
                nEnd = nMid - 1;
                nMid = (nStart + nEnd) / 2;
            }
        }
        
        if (V[nMid] <= val) // val is not in the vector V, nMid element is smaller than or equal to val.
        {
            V.insert(V.begin() + nMid + 1, val);
        }
        else                // val is not in the vector V, nMid element is larger than val.
        {
            V.insert(V.begin() + nMid, val);
        }
        
        return V[V.size() - (nKth)];
    }
};
 
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

---

정답코드 II: Using Min Heap

class KthLargest {
public:
    priority_queue <int, vector<int>, greater<int>> min_heap;
    int nKth;
    
    KthLargest(int k, vector<int>& nums) {
        int nCount = nums.size();
        nKth = k;
        int nIterCount = (k < nCount) ? k : nCount;
        
        sort(nums.begin(), nums.end());
        
        // if initial nums count is smaller than K, push every value to the min_heap.
        // otherwise push largest K values to the min_heap
        for(int i = 1; i <= nIterCount ; i++)
        {
            min_heap.push(nums[nCount - i]);
        }
    }
    
    int add(int val) {
        int nRet = 0;
        
        // if heap size is smaller than K, push node
        if (min_heap.size() < nKth)
        {
            min_heap.push(val);
        }
        else
        {
            // if smallest element so far is smaller than the new value,
            // pop the element and push the new value to the min_heap.
            if (min_heap.top() < val)
            {
                min_heap.pop();
                min_heap.push(val);
            }
        }
        
        // return the minimum value
        nRet = min_heap.top();
        return nRet;
    }
};

 

핵심 Idea: 

Kth largest value == Kth smallest value of the largest K values.

to find a smallest value in a min heap takes O(1) time.

When initializing, we can sort the given nums stream and create a min heap using only the top K values.

Everytime add function is called, we can compare the new given value with the minimum value of the min heap.

If the minimum value of the heap is smaller, we can get rid of that value and add the new value.

For the return value of the add function, we simply return the minimum value of the min heap.

 

원본 링크: https://leetcode.com/problems/kth-largest-element-in-a-stream/