LeetCode-347. Top K Frequent Elements

LeetCode-347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

Example 2:

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

Note:

You may assumekis always valid, 1 ≤k≤ number of unique elements.Your algorithm's time complexitymust bebetter than O(nlogn), wherenis the array's size.

题解：

使用桶排序，时间复杂度O(n)

class Solution {public: vector topKFrequent(vector& nums, int k) { unordered_map m; int n = nums.size(); vector> bucket(n + 1); for (int i = 0; i < n; i++) { m[nums[i]]++; } for (auto it = m.begin(); it != m.end(); it++) { bucket[n - it->second].push_back(it->first); } vector res; int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < bucket[i].size(); j++) { cnt++; res.push_back(bucket[i][j]); if (cnt == k) { return res; } } } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。