问题描述：给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。
//思路一：桶排序
//设置若干个桶，每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率，即第 i 个桶中存储的数出现的频率为 i。
//把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
//统计数组中元素出现频率
HashMap<Integer,Integer> map = new HashMap<>();
for(int num : nums){
map.put(num, map.getOrDefault(num,0)+1);
}
//每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率
List<Integer>[] buckets = new ArrayList[nums.length+1];
for(Integer num : map.keySet()){
Integer freq = map.get(num);
if(buckets[freq] == null){
buckets[freq] = new ArrayList<>();
}
buckets[freq].add(num);
}
List<Integer> res = new ArrayList<>();
for(int i=buckets.length-1;i>=0 && res.size()<k;i--){
if(buckets[i]==null){
continue;
}
if(buckets[i].size() <= (k-res.size())){
res.addAll(buckets[i]);
}else{
res.addAll(buckets[i].subList(0,k-res.size()));
}
}
return res;
}
}//思路二：堆排序
//利用堆排序
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){
int freq = map.getOrDefault(num,0);
map.put(num,++freq);
}
Set<Integer> set = map.keySet();
Element[] elements = new Element[set.size()];
int i=0;
for(Integer key : set){
elements[i] = new Element(key,map.get(key));
i++;
}
PriorityQueue<Element> pq = new PriorityQueue<>();
for(Element element : elements){
pq.add(element);
if(pq.size() > k){
pq.poll();
}
}
while(!pq.isEmpty()){
Element element = pq.poll();
res.add(element.num);
}
return res;
}
}
class Element implements Comparable<Element>{
int num;
int freq;
Element(int num,int freq){
this.num = num;
this.freq = freq;
}
@Override
public int compareTo(Element o) {
return this.freq - o.freq;
}
}问题描述：给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
"Aabb"
输出:
"bbAa"
解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。
class Solution {
public String frequencySort(String s) {
//统计 s 中字符串出现的次数
HashMap<Character,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
map.put(c,map.getOrDefault(c,0)+1);
}
List<Character>[] buckets = new ArrayList[s.length()+1];
for(Character c : map.keySet()){
Integer freq = map.get(c);
if(buckets[freq]==null){
buckets[freq] = new ArrayList<>();
}
buckets[freq].add(c);
}
StringBuilder res = new StringBuilder();
for(int freq = buckets.length-1;freq>=0;freq--){
if(buckets[freq] == null){
continue;
}
List<Character> list = buckets[freq]; //list 中所有元素都出现了 freq 次数
for(Character c : list){
for(int i=0;i<freq;i++){
res.append(c);
}
}
}
return res.toString();
}
}
问题描述：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
- 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
//思路如上图：
//i指向值为0的元素，swap(i,zero+1) ,交换后，i位置元素是1(nums[zero+1..i+1]==1)，
//不需要处理，i直接+1
//i指向值为1的元素，不需要处理直接+1
//i指向值为2的元素，swap(i,two-1),交换后，two-1位置元素就是2
public void sortColors(int[] nums) {
int zero = -1;
int two = nums.length;
int i = 0;
while(i<two){
if(nums[i] ==0){
zero++;
swap(nums,zero,i);
i++;
}else if(nums[i] ==2){
two--;
swap(nums,two,i);
}else{
i++;
}
}
}
private void swap(int[] nums,int i,int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
问题描述：在未排序的数组中找到第 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、注意：这里求的是求第k个最大元素，就是求(nums.length-k+1)个最小元素
//2、求第m小的元素，是非常典型的快速排序的应用
public int findKthLargest(int[] nums, int k) {
//1 <= k <= nums.length
k = nums.length - k + 1; //转化为第k小元素问题
int lo = 0;
int hi = nums.length -1;
while(lo<=hi){
int p = partition(nums,lo,hi);
if(p == k-1){
return nums[p];
}else if(p<(k-1)){
lo++;
}else{ //p> k-1
assert p > (k-1);
hi--;
}
}
return nums[0];
}
private int partition(int[] nums,int l,int r){
int pivot = nums[l];
while(l < r){
//从右向左查找第一个 < pivot 的元素
while(l < r && nums[r] >= pivot){
r--;
}
nums[l] = nums[r];
//从左向右查找第一个 > pivot 的元素
while(l < r && nums[l] <= pivot){
l++;
}
nums[r] = nums[l];
}
nums[l] = pivot;
return l;
}