347. Top K Frequent Elements

Question

LeetCode Problem

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]
Example 3:
Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2
Output: [1,2]
Constraints:

• 1 <= nums.length <= 10 5
• -10 4 <= nums[i] <= 10 4
• 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.

Solutions

void partition (vector<pair<int, int>> freqVec, int left, int right, int& lt, int& rt) {
	int pivotFreq = freqVec[right].second;
	lt = left;
	int mid = left;
	rt = right;
	while (mid <= rt) {
		const auto& midFreq = freqVec[mid].second;
		if (midFreq > pivotFreq) {
			swap(freqVec[mid], freqVec[lt]);
			++mid;l
			++lt;
		} else if (midFreq < pivotFreq) {
			swap(freqVec[mid], freqVec[rt]);
			--rt;
		} else {
			++mid;
		}
	}
}

vector<int> topKFrequent(vector<int>& nums, int k) {
	unordered_map<int, int> freqMap;
	for (int i : nums) {
		freqMap[i] += 1;
	}
	vector<pair<int, int>> freqVec;
	for (const auto& [number, frequency] : freqMap) {
		freqVec.push_back({number, frequency});
	}
	
	int n = static_cast<int>(freqVec.size());
	int left = 0;
	int right = n - 1;
	int target = k - 1;
	while (left <= right) {
		int lt = 0;
		int rt = 0;
		partition(freqVec, left, right, lt, rt);
		if (target < lt) {
			right = lt - 1;
		} else if (target > rt) {
			left = rt + 1;
		} else {
			vector<int> ret;
			for (int i = 0; i <= target; ++i) {
				ret.push_back(freqVec[i].first);
			}
			return ret;
		}
	}
	// should never enter.
	return vector<int>{};
}