2023-05-22 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 22

Description

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

 

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  using pi = pair<int, int>;
public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
    map<int, int> count;
    for(auto n : nums) {
      count[n] += 1;
    }
    priority_queue<pi, vector<pi>, greater<pi>> pq;
    for(auto [n, c] : count) {
      pq.push({c, n});
      if(pq.size() > k) pq.pop();
    }
    vector<int> answer;
    answer.reserve(k);
    while(pq.size()) {
      answer.push_back(pq.top().second);
      pq.pop();
    }
    return answer;
  }
};

// Accepted
// 21/21 cases passed (15 ms)
// Your runtime beats 86.09 % of cpp submissions
// Your memory usage beats 71.77 % of cpp submissions (13.6 MB)
Algorithm