上一篇leetcode专题，通过一道算法题，疏导了一下快速排序算法的知识点，今天根据leetcode的347整理一下桶排序的算法思路。
正文开始
题目：
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
解题思路：
这道题是根据给定的数组，返回出现次数前k位的数。需要注意的是返回的是出现频率大小的前k位，因此返回数组长度是大于等于k的。之前我就是在这个地方卡了很久。
解题思路是：
1、使用hashMap存储数组元素和出现次数。
2、新建一个由arrayList集合组成的数组 temp，数组大小为给定数组长度+1；
3、遍历map的key，将出现频次相同的key值放置于temp的list中，下标为出现频次，这样保证了下标是排好序的。
4、逆序遍历数组 temp，得到前k个list中的key值。
代码：
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> temp = new HashMap<>();
ArrayList<Integer> result = new ArrayList<>();
for(int i : nums){//记录每个元素出现的次数
if(temp.containsKey(i)){
int flag = temp.get(i);
temp.put(i,flag + 1);
}else{
temp.put(i,1);
}
}
//新建len+1个桶，桶中存放出现对应次数的nums[i]
ArrayList[] list = new ArrayList[nums.length + 1];
for(int key : temp.keySet()){
int count = temp.get(key);
if(list[count] == null){
list[count] = new ArrayList<Integer>();
}
list[count].add(key);
}
for(int i = list.length - 1; i>=0; i --){
if(list[i] != null && result.size() < k){
result.addAll(list[i]);
}
}
return result;
}
}
算法思想：
这里使用到的算法是
桶排序：核心思想是，将元素放置在有限个有序桶里面，，然后再对桶里面的元素排序，最后按照桶的顺序合理的输出元素。用通俗语言来讲就是，将一定范围中的数组划分几个子范围，再子范围中再排序，可以使用其他排序方法，也可以使用递归继续使用桶排序。
应用到这道题里，其实只用了算法的前一半。如果将题目改成：返回长度为k的数组，保证数组前一个元素的出现频次大于等于后一次元素出现的频次，在原来基础上，需要将桶子里面的数组再排序。
