Top K Frequent Elements (M)
題目
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.
- It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
- You can return the answer in any order.
題意
求一個陣列中出現次數最多的前k個元素，要求時間復雜度小于\(O(NlogN)\)，
思路
最直接的方法是維護一個最大大小為k的小頂堆，向其中添加陣列中的不重復元素，按照出現次數排序，如果添加后堆大小為k+1，則將堆頂元素去除，這樣最終留下的就是k個出現次數最多的元素，復雜度為\(O(Nlogk)\)，
top k型別的問題還可以用 快速選擇演算法 來解決，平均復雜度為\(O(N)\)，
代碼實作
Java
優先佇列
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> record = new HashMap<>();
Queue<Integer> q = new PriorityQueue<>((a, b) -> record.get(a) - record.get(b));
for (int num : nums) {
record.put(num, record.getOrDefault(num, 0) + 1);
}
for (int num : record.keySet()) {
q.offer(num);
if (q.size() > k) {
q.poll();
}
}
int[] res = new int[k];
int i = 0;
while (!q.isEmpty()) {
res[i++] = q.poll();
}
return res;
}
}
快速選擇
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> record = new HashMap<>();
for (int num : nums) {
record.put(num, record.getOrDefault(num, 0) + 1);
}
int[] arr = new int[record.size()];
int i = 0;
for (int num : record.keySet()) {
arr[i++] = num;
}
int left = 0, right = arr.length - 1;
int[] res = new int[k];
while (left <= right) {
int mid = partition(arr, left, right, record);
if (k - 1 < mid) {
right = mid - 1;
} else if (k - 1 > mid) {
left = mid + 1;
} else {
for (int j = 0; j < k; j++) {
res[j] = arr[j];
}
return res;
}
}
return res;
}
private int partition(int[] arr, int left, int right, Map<Integer, Integer> record) {
int tmp = arr[left];
while (left < right) {
while (left < right && record.get(arr[right]) < record.get(tmp)) {
right--;
}
arr[left] = arr[right];
while (left < right && record.get(arr[left]) >= record.get(tmp)) {
left++;
}
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/33849.html
標籤：其他