给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:
输入: nums = [1], k = 1 输出: [1]
提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。 你可以按任意顺序返回答案。
一开始只想到了暴力
了解了Java中的 PriorityQueue< Integer >后，想出了如下方法（大顶堆）
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer,Integer> map=new HashMap<>(); int max=1; for(int i=0;i<nums.length;i++){ if(map.containsKey(nums[i]))map.put(nums[i],map.get(nums[i])+1); else map.put(nums[i],1); } PriorityQueue<Integer> pq=new PriorityQueue<>((o1,o2)->map.get(o2)-map.get(o1)); for(Integer key:map.keySet()){ pq.offer(key); } int[] result=new int[k]; for(int i=0;i<k;i++)result[i]=pq.poll(); return result; } }1、哈希+堆
class Solution { public List<Integer> topKFrequent(int[] nums, int k) { // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值 HashMap<Integer,Integer> map = new HashMap(); for(int num : nums){ if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } // 遍历map，用最小堆保存频率最大的k个元素 PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return map.get(a) - map.get(b); } }); for (Integer key : map.keySet()) { if (pq.size() < k) { pq.add(key); } else if (map.get(key) > map.get(pq.peek())) { pq.remove(); pq.add(key); } } // 取出最小堆中的元素 List<Integer> res = new ArrayList<>(); while (!pq.isEmpty()) { res.add(pq.remove()); } return res; } }2、
//基于桶排序求解「前 K 个高频元素」 class Solution { public List<Integer> topKFrequent(int[] nums, int k) { List<Integer> res = new ArrayList(); // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值 HashMap<Integer,Integer> map = new HashMap(); for(int num : nums){ if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } //桶排序 //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标 List<Integer>[] list = new List[nums.length+1]; for(int key : map.keySet()){ // 获取出现的次数作为下标 int i = map.get(key); if(list[i] == null){ list[i] = new ArrayList(); } list[i].add(key); } // 倒序遍历数组获取出现顺序从大到小的排列 for(int i = list.length - 1;i >= 0 && res.size() < k;i--){ if(list[i] == null) continue; res.addAll(list[i]); } return res; } }作者：MisterBooo 链接：link 来源：力扣（LeetCode）
3、快排变形
class Solution { public int[] topKFrequent(int[] nums, int k) { // 统计每个数字出现的次数 Map<Integer, Integer> counterMap = IntStream.of(nums).boxed().collect(Collectors.toMap(e -> e, e -> 1, Integer::sum)); // 构造Pair数组，Pair.num 表示数值，Pair.freq 表示数字出现的次数 Pair[] pairs = IntStream.of(nums).distinct().boxed().map(num -> new Pair(num, counterMap.get(num))).toArray(Pair[]::new); // 使用快排变形 O(N) 获取Pair数组中频次最大的 k 个元素（第 4 个参数是下标，因此是 k - 1）。 Pair[] topKPairs = quickSelect(pairs, 0, pairs.length - 1, k - 1); // 构造返回结果 int[] res = new int[k]; int idx = 0; for (Pair pair: topKPairs) { res[idx++] = pair.num; } return res; } private Pair[] quickSelect(Pair[] pairs, int lo, int hi, int idx) { if (lo > hi) { return new Pair[0]; } // 快排切分后，j 左边的数字出现的次数都大于等于 pairs[j].freq，j 右边的数字出现的次数都小于等于 pairs[j].freq。 int j = partition(pairs, lo, hi); // 如果 j 正好等于目标idx，说明当前pairs数组中的[0, idx]就是出现次数最大的 K 个元素。 if (j == idx) { return Arrays.copyOf(pairs, idx + 1); } // 否则根据 j 与 idx 的大小关系判断找左段还是右段 return j < idx? quickSelect(pairs, j + 1, hi, idx): quickSelect(pairs, lo, j - 1, idx); } private int partition(Pair[] pairs, int lo, int hi) { Pair v = pairs[lo]; int i = lo, j = hi + 1; while (true) { while(++i <= hi && pairs[i].freq > v.freq); while(--j >= lo && pairs[j].freq < v.freq); if (i >= j) { break; } Pair tmp = pairs[i]; pairs[i] = pairs[j]; pairs[j] = tmp; } pairs[lo] = pairs[j]; pairs[j] = v; return j; } } class Pair { int num; int freq; public Pair(int num, int freq) { this.num = num; this.freq = freq; } }作者：sweetiee 链接：link 来源：力扣（LeetCode）
1、堆
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer,Integer> map=new HashMap<>(); int max=1; for(int i=0;i<nums.length;i++){ if(map.containsKey(nums[i]))map.put(nums[i],map.get(nums[i])+1); else map.put(nums[i],1); } PriorityQueue<Integer> pq=new PriorityQueue<>((o1,o2)->map.get(o1)-map.get(o2)); for(Integer key:map.keySet()){ if(pq.size()<k)pq.offer(key); else if(map.get(key)>map.get(pq.peek())){ pq.poll(); pq.offer(key); } } int[] result=new int[k]; for(int i=0;i<k;i++)result[i]=pq.poll(); return result; } }2、桶排序 ①、使用双层List，
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer,Integer> map=new HashMap<>(); List<List<Integer>> tong=new ArrayList<>(); for(int i=0;i<nums.length;i++){ if(map.containsKey(nums[i]))map.put(nums[i],map.get(nums[i])+1); else map.put(nums[i],1); tong.add(new ArrayList<Integer>()); } tong.add(new ArrayList<Integer>()); for(Integer key:map.keySet()){ tong.get(map.get(key)).add(key); } int[] result=new int[k]; int index=0; for(int i=nums.length;i>0;i--){ for(int j=0;j<tong.get(i).size();j++){ if(index==k)return result; result[index++]=tong.get(i).get(j); } } return result; } }②使用List数组，降低空间复杂度（没东西的桶中为null，而不是空List了）
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer,Integer> map=new HashMap<>(); List<Integer>[] tong=new List[nums.length+1]; for(int i=0;i<nums.length;i++){ if(map.containsKey(nums[i]))map.put(nums[i],map.get(nums[i])+1); else map.put(nums[i],1); } for(Integer key:map.keySet()){ if(tong[map.get(key)]==null)tong[map.get(key)]=new ArrayList<Integer>(); tong[map.get(key)].add(key); } int[] result=new int[k]; int index=0; for(int i=nums.length;i>0;i--){ if(tong[i]==null)continue; for(int j=0;j<tong[i].size();j++){ if(index==k)return result; result[index++]=tong[i].get(j); } } return result; } }HashMap:map.keySet()获取全部key
java中的堆：
PriorityQueue（优先队列）详解
PriorityQueue< Integer > pq=new PriorityQueue<>((o1,o2)->map.get(o1)-map.get(o2));
方法：pq.offer(key);pq.poll();pq.size();pq.peek();
快排思想：排序总结
桶排序：桶排序
使用List数组，避免不必要的new ArrayList< Integer>()
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
1、排序
class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length-k]; } }2、堆
class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> pq=new PriorityQueue<>(); for(int i=0;i<nums.length;i++){ if(i<k)pq.offer(nums[i]); else if(nums[i]>pq.peek()){ pq.poll(); pq.offer(nums[i]); } } return pq.peek(); } }1、堆（优化），根据 k 的不同，选最大堆和最小堆，目的是让堆中的元素更小
import java.util.PriorityQueue; public class Solution { // 根据 k 的不同，选最大堆和最小堆，目的是让堆中的元素更小 // 思路 1：k 要是更靠近 0 的话，此时 k 是一个较大的数，用最大堆 // 例如在一个有 6 个元素的数组里找第 5 大的元素 // 思路 2：k 要是更靠近 len 的话，用最小堆 // 所以分界点就是 k = len - k public int findKthLargest(int[] nums, int k) { int len = nums.length; if (k <= len - k) { // System.out.println("使用最小堆"); // 特例：k = 1，用容量为 k 的最小堆 // 使用一个含有 k 个元素的最小堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b); for (int i = 0; i < k; i++) { minHeap.add(nums[i]); } for (int i = k; i < len; i++) { // 看一眼，不拿出，因为有可能没有必要替换 Integer topEle = minHeap.peek(); // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去 if (nums[i] > topEle) { minHeap.poll(); minHeap.add(nums[i]); } } return minHeap.peek(); } else { // System.out.println("使用最大堆"); assert k > len - k; // 特例：k = 100，用容量为 len - k + 1 的最大堆 int capacity = len - k + 1; PriorityQueue<Integer> maxHeap = new PriorityQueue<>(capacity, (a, b) -> b - a); for (int i = 0; i < capacity; i++) { maxHeap.add(nums[i]); } for (int i = capacity; i < len; i++) { // 看一眼，不拿出，因为有可能没有必要替换 Integer topEle = maxHeap.peek(); // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去 if (nums[i] < topEle) { maxHeap.poll(); maxHeap.add(nums[i]); } } return maxHeap.peek(); } } }2、
import java.util.Random; public class Solution { private static Random random = new Random(System.currentTimeMillis()); public int findKthLargest(int[] nums, int k) { int len = nums.length; int left = 0; int right = len - 1; // 转换一下，第 k 大元素的索引是 len - k int target = len - k; while (true) { int index = partition(nums, left, right); if (index == target) { return nums[index]; } else if (index < target) { left = index + 1; } else { right = index - 1; } } } public int partition(int[] nums, int left, int right) { // 在区间随机选择一个元素作为标定点 if (right > left) { int randomIndex = left + 1 + random.nextInt(right - left); swap(nums, left, randomIndex); } int pivot = nums[left]; // 将等于 pivot 的元素分散到两边 // [left, lt) <= pivot // (rt, right] >= pivot int lt = left + 1; int rt = right; while (true) { while (lt <= rt && nums[lt] < pivot) { lt++; } while (lt <= rt && nums[rt] > pivot) { rt--; } if (lt > rt) { break; } swap(nums, lt, rt); lt++; rt--; } swap(nums, left, rt); return rt; } private void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } }作者：liweiwei1419 链接：link 来源：力扣（LeetCode）
堆：最大堆与最小堆结合运用
快排思想：排序总结
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入: “tree”
输出: “eert”
解释: 'e’出现两次，'r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。 示例 2:
输入: “cccaaa”
输出: “cccaaa”
解释: 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。 示例 3:
输入: “Aabb”
输出: “bbAa”
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意’A’和’a’被认为是两种不同的字符。
1、
public String frequencySort(String s) { Map<Character, Integer> frequencyForNum = new HashMap<>(); for (char c : s.toCharArray()) frequencyForNum.put(c, frequencyForNum.getOrDefault(c, 0) + 1); List<Character>[] frequencyBucket = new ArrayList[s.length() + 1]; for (char c : frequencyForNum.keySet()) { int f = frequencyForNum.get(c); if (frequencyBucket[f] == null) { frequencyBucket[f] = new ArrayList<>(); } frequencyBucket[f].add(c); } StringBuilder str = new StringBuilder(); for (int i = frequencyBucket.length - 1; i >= 0; i--) { if (frequencyBucket[i] == null) { continue; } for (char c : frequencyBucket[i]) { for (int j = 0; j < i; j++) { str.append(c); } } } return str.toString(); }2、堆
class Solution { public String frequencySort(String s) { int[] letters = new int[128]; for (char c : s.toCharArray()) letters[c]++; PriorityQueue<Character> heap = new PriorityQueue<>(128, (a, b) -> Integer.compare(letters[b], letters[a])); StringBuilder res = new StringBuilder(); for (int i = 0; i < letters.length; ++i) { if (letters[i] != 0) { heap.offer((char)i); } } while (!heap.isEmpty()) { char c = heap.poll(); while (letters[c]-- > 0) { res.append(c); } } return res.toString(); } }作者：CHRIS_WiNG 链接：link 来源：力扣（LeetCode）
桶排序
堆
荷兰国旗包含三种颜色：红、白、蓝。
有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排列。它其实是三向切分快速排序的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素、等于切分元素、大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？
计数排序：
class Solution { public void sortColors(int[] nums) { int[] Num=new int[3]; for(int i=0;i<nums.length;i++){ if(nums[i]==0)Num[0]++; else if(nums[i]==1)Num[1]++; else if(nums[i]==2)Num[2]++; } int index=0; for(int i=0;i<=2;i++){ for(int j=0;j<Num[i];j++)nums[index++]=i; } } }作者：liweiwei1419 链接：link 来源：力扣（LeetCode）
计数排序 计数排序
快排中的partition思想
