Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> mp;
for (int i : nums)
mp[i]++;
vector<pair<int, int>> v(mp.begin(), mp.end());
sort(v.begin(), v.end(), cmp);
vector<int> ans;
for (int i = 0; i < k; ++i)
ans.push_back(v[i].first);
return ans;
}
private:
static bool cmp(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
};
In order to sort the map with it's value, we can't sort it directly because the iterator type on std::unordered_map is a ForwardIterator, not a RandomAccessIterator, so the first requirement is unsatisfied. The type of the dereferenced iterator is pair<const Key, T>, which is not MoveAssignable (can't assign to const), so the second requirement is also unsatisfied.
we can use a vector to contain the unordered_map, then sort the vector.
Approach #2: Java.
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer>[] bucket = new List[nums.length+1];
Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
for (int n : nums) {
frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
}
for (int key : frequencyMap.keySet()) {
int frequency = frequencyMap.get(key);
if (bucket[frequency] == null)
bucket[frequency] = new ArrayList<>();
bucket[frequency].add(key);
}
List<Integer> res = new ArrayList<>();
for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; --pos) {
if (bucket[pos] != null)
res.addAll(bucket[pos]);
}
return res;
}
}
Approach #3: Python.
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
return zip(*collections.Counter(nums).most_common(k))[0]
11.Use Counter to extract the top k frequent elements, most_common(k) return a list of tuples, where the first item of the tuple is the element, and the second item of the tuple is the count, Thus,the built-in zip function could be used to extract the first item from the tuples
| Time Submitted | Status | Runtime | Language |
|---|---|---|---|
| 3 minutes ago | Accepted | 40 ms | python |
| 5 minutes ago | Accepted | 12 ms | java |
| 20 minutes ago | Accepted | 12 ms | cpp |