1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
|
import java.net.Inet4Address; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue;
class Solution { public int[] topKFrequent(int[] nums, int k) { HashMap<Integer,Integer> map = new HashMap<>(); for(int num : nums){ map.put(num,map.getOrDefault(num,0)+1); } PriorityQueue<Map.Entry<Integer,Integer>> minHeap = new PriorityQueue<>( (a,b) ->(a.getValue() - b.getValue()) ); for(Map.Entry<Integer,Integer> entry : map.entrySet()){ minHeap.offer(entry); if(minHeap.size() > k){ minHeap.poll(); } } int[] ans = new int[k]; for(int i = 0; i<k; i++){ ans[i] = minHeap.poll().getKey(); } return ans; } }
import java.util.HashMap; import java.util.Map; import java.util.Random;
class Solution { public int[] topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); }
int[] frequencies = new int[map.size()]; int index = 0; for (int frequency : map.values()) { frequencies[index++] = frequency; }
int kthLargestFrequency = quickSelect(frequencies, 0, frequencies.length - 1, frequencies.length - k);
int[] ans = new int[k]; index = 0; for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() >= kthLargestFrequency) { ans[index++] = entry.getKey(); } } return ans; }
private int quickSelect(int[] nums, int left, int right, int k) { if (left == right) { return nums[left]; }
int pivotIndex = randomPartition(nums, left, right);
if (pivotIndex == k) { return nums[pivotIndex]; } else if (pivotIndex < k) { return quickSelect(nums, pivotIndex + 1, right, k); } else { return quickSelect(nums, left, pivotIndex - 1, k); } }
private int randomPartition(int[] nums, int left, int right) { Random random = new Random(); int pivotIndex = random.nextInt(right - left + 1) + left;
swap(nums, pivotIndex, right);
int pivot = nums[right]; int i = left;
for (int j = left; j < right; j++) { if (nums[j] <= pivot) { swap(nums, i, j); i++; } }
swap(nums, i, right);
return i; }
private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
|