703. Kth Largest Element in a Stream

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

Kth Largest Element in a Stream - LeetCode

 

k 번째 엘리먼트를 출력하는 add 함수를 만드는 문제입니다.

모든 원소를 삽입할 필요 없이 k 번째까지만 삽입하고 k개 이상일 때 가장 작은 값을 삭제하는 식으로 풀이가 나은 듯

 

priority_queue & set 비교

Dicussion에 있는 풀이

class KthLargest {
public:
    
    // use min heap, keep only max k elements rest delete them time and again ...
    priority_queue<int, vector<int>, greater<int>> pq;
    int size;
    KthLargest(int k, vector<int> nums) {
        size=k;
        for(auto x:nums) {
            pq.push(x);
        }
        while(pq.size()>k)
            pq.pop();
    }
    
    int add(int val) {
        pq.push(val);
        if(pq.size()>size) pq.pop();
        return pq.top();
    }
};

 

bruth-force 풀이

매 삽입시마다 sort 비용이 발생하여 time limit 시간 초과가 발생합니다.

class KthLargest {
public:
	KthLargest(int k, vector<int>& nums) {
		this->key = k;
		vi = nums;
	}

	int add(int val) {
		vi.push_back(val);
        sort(vi.begin(), vi.end(), greater<int>());
		return vi[key - 1];
	}
	int key;
	vector<int> vi;
};

 

multimap을 활용한 풀이

중복을 허용하는 multimap에 특성과 삽입하면서 내림차순으로 정렬되는 특성을 활용.

add 함수에서 k 번째 큰 수를 출력을 하기 위해 reverse_iterator 사용하여 k 만큼 이동후 반환

class KthLargest {
public:
    KthLargest(int k, const vector<int>& nums) {
        this->key = k;
        for (auto a : nums) {
            m.insert(pair<int, int>(a, a));
        }
    }

    int add(int val) {
        m.insert(pair<int, int>(val, val));

        multimap<int, int>::reverse_iterator it = m.rbegin();
        for (int i = 0; i < key-1; i++) {
            it++;
        }

        return it->first;
    }

    int key;
    multimap<int, int> m;
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

 

O 풀이

multiset 활용

class KthLargest {
private:
   multiset<int> m_oSet;
   int m_KIndex;
   int m_kNums;
public:
   KthLargest(int k, vector<int>& nums) {
      m_KIndex = k - 1;

      sort(nums.begin(), nums.end(), greater<int>());      
      int nInputCnt = nums.size() < k ? nums.size() : k;

      for( int i = 0; i < nInputCnt; i++ )
         m_oSet.insert(nums.at(i));      

      if( m_oSet.size() <= m_KIndex ) //k번째 보다 데이터가 적은 경우
         return;
   
      m_kNums = *m_oSet.begin();
   }

   int add(int val) {
      if( m_oSet.size() <= m_KIndex ) //k번째 보다 데이터가 적은 경우
      {
         m_oSet.insert(val);
         m_kNums = *m_oSet.begin();
         return m_kNums;
      }

      if( val < m_kNums ) //작은 값 무시
         return m_kNums;

      m_oSet.insert(val);
      m_oSet.erase(m_oSet.begin());

      m_kNums = *m_oSet.begin();
      return m_kNums;
   }
};

 

B 풀이

전체 정렬 안 하고 파셜 SORT를 사용하여 전체 정렬을 회피

class KthLargest {
public:
    int m_k;
    priority_queue<int, vector<int>, greater<int>> m_minHeap;
    KthLargest(int k, vector<int>& nums) {
        m_k = k;
        if (nums.size() == 0)
            return;
        // 내림차순 정렬한다. 큰순으로 k 개만 필요하다.
        // nums 가 3개 있는데 4개까지 정렬해라 하면 죽는다. ㅠㅠ
        partial_sort(nums.begin(), nums.begin() + min(k, int(nums.size())), nums.end(), greater<int>());
        //sort(nums.begin(), nums.end(), greater<int>());
        for (int i = 0; i < min(k, (int)(nums.size())); ++i)
            m_minHeap.push(nums[i]);
    }

    int add(int val) {
        m_minHeap.push(val);
        if (m_minHeap.size() > m_k)
            m_minHeap.pop();
        return m_minHeap.top();
    }
};

 

W 풀이

vector 를 활용한 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class KthLargest {
public:
    KthLargest(int k, vector<int> &nums) : NUMS(nums), idx(k) {
        // sort NUMS
        NUMS.push_back(-987654321);
        NUMS.push_back(987654321);
        sort(NUMS.begin(), NUMS.end());
    }

    // vector는 정렬되어 있음.
    // add 할 데이터의 index 구하기.
    // vector insert.
    // kth Largest 반환.

    int findPos(int val, int a, int b) {
        if (a == b)
            return b;

        int i = (a + b) / 2;
        if (val == NUMS[i])
            return i;

        if (val > NUMS[i]) {
            if (i == b)
                return i;
            return findPos(val, i + 1, b);
        }

        if (i == a)
            return i;

        if (NUMS[i - 1] < val)
            return i;
        
        return findPos(val, a, i - 1);
    }

    int add(int val) {
        int i = findPos(val, 0, NUMS.size() - 1);
        vector<int>::iterator it = NUMS.begin();
        while (--i >= 0)
            it++;

        NUMS.insert(it, val);
        return NUMS[NUMS.size() - idx - 1];
    }

private:
    vector<int> &NUMS;
    int idx;
};

 

Z 풀이

바이너리 서치 사용 upperbound

bool desc(int a, int b) { return a > b; }

class KthLargest {
public:
    KthLargest(int k, vector<int>& nums)
        : m_nkTh(k)
    {
        sort(nums.begin(), nums.end(), desc);
        int nLength = k < nums.size() ? k : nums.size();
        for( int i = 0 ; i < nLength; i++) // 필요한 크기만 사용
            m_list.push_back(nums[i]);
    }

    int add(int val) 
    {
        insert(val);

        if (m_list.size() < m_nkTh) // 리스트가 부족한 경우
            return -1;
        else
            return m_list[m_nkTh - 1];

    }

    void insert(int val)
    {
        if (m_list.size() >= m_nkTh) // 리스트가 가득차 있는 경우
        {
            if (m_list[m_nkTh - 1] < val)
                m_list.pop_back();
            else
                return;
        }

        vector<int>::iterator pos = upper_bound(m_list.begin(), m_list.end(), val, desc); // 탐색
        m_list.insert(pos, val); // 추가
    }

    int m_nkTh;
    vector<int> m_list;
};