二刷 06/2022
Version #3 Quick Select
和973用了不同的partition方法
这里没有把pivot swap到它正确的位置
返回的index是left - 1, 表示从(0-index) >= partition, (index+1, len-1) <= partition
如果index<k-1表示从0到index不足k个数，这时候要start=index+1，如果不+1会infinite loop
表示从0到index有大于等于k个数，这时候要end=index
Time O(N)
Space O(#distinct number)
Runtime: 16 ms, faster than 58.05% of Java online submissions for Top K Frequent Elements.
Memory Usage: 50.2 MB, less than 59.80% of Java online submissions for Top K Frequent Elements.
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[0];
}
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
int[] unique = new int[count.size()];
int i = 0;
for (int num : count.keySet()) {
unique[i++] = num;
}
int index = unique.length;
int start = 0, end = unique.length - 1;
while (index != k - 1) {
index = partition(unique, start, end, count);
// System.out.printf("start=%d,end=%d,index=%d\n", start, end, index);
if (index < k - 1) {
start = index + 1;
} else {
end = index;
}
}
int[] result = new int[k];
for (int j = 0; j < k; j++) {
result[j] = unique[j];
}
return result;
}
private int partition(int[] nums, int start, int end, Map<Integer, Integer> count) {
int pivot = nums[start + (end - start) / 2];
int pivotCnt = count.get(pivot);
int left = start, right = end;
while (left <= right) {
while (left <= right && count.get(nums[left]) > pivotCnt) {
left++;
}
while (left <= right && count.get(nums[right]) < pivotCnt) {
right--;
}
if (left <= right) {
swap(nums, left, right);
left++;
right--;
}
}
return left - 1;
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
有一个bug
因为count 是从1开始，所以生成的bucket size 需要 是length + 1
Time O(n)
95.43 %
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
// key-num, value-count
for (int num : nums) {
map.put(num, 1 + map.getOrDefault(num, 0));
}
// the frequency can't exceed total number of nums
List<Integer>[] bucket = new List[nums.length + 1];
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int count = entry.getValue();
if (bucket[count] == null) {
bucket[count] = new ArrayList<>();
}
bucket[count].add(entry.getKey());
}
List<Integer> result = new ArrayList<>();
int i = nums.length;
while (i >= 0 && result.size() < k) {
if (bucket[i] != null) {
result.addAll(bucket[i]);
}
i--;
}
return result;
}
}
Version #1 HashMap + minHeap
Time O(nlogk)
Space O(count of unique values)
51.98 %
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// Count frequency -> Map<num, count> -> O(n) for all nums
// get most k count
// retrieve from map
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
int count = 1 + map.getOrDefault(num, 0);
map.put(num, count);
}
// O(nlogk)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int count : map.values()) {
if (minHeap.size() < k) {
minHeap.offer(count);
} else if (count > minHeap.peek()) {
minHeap.poll();
minHeap.offer(count);
}
}
Set<Integer> countK = new HashSet<>(minHeap);
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (countK.contains(entry.getValue())) {
result.add(entry.getKey());
}
}
return result;
}
}
No comments:
Post a Comment