1，先排序
这种实现方式比较简单，无论使用哪种排序方式都可以，排序之后在取前k个元素即可，代码如下
public ArrayList<integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<integer> res = new ArrayList<>(k);
//根据题意要求，如果K>数组的长度，返回一个空的数组
if (k > input.length)
return res;
//先排序，然后选择前k个即可
Arrays.sort(input);
for (int i = 0; i < k; ++i) {
res.add(input[i]);
}
return res;
}
2，使用最大堆
我们要保证堆的大小不能超过K，然后遍历数组，因为是最大堆，也就是堆顶元素是堆中最大的，如果遍历的元素小于堆顶元素，就把堆顶元素给移除，然后再把当前遍历的元素加入到堆中，最后在把堆中元素转化为数组即可。
public ArrayList<integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<integer> res = new ArrayList<>(k);
//根据题意要求，如果K>数组的长度，返回一个空的数组
if (k > input.length || k == 0)
return res;
//创建最大堆
PriorityQueue<integer> queue = new PriorityQueue<>((num1, num2) -> num2 - num1);
//先在堆中放数组的前k个元素
for (int i = 0; i < k; ++i) {
queue.offer(input[i]);
}
//因为是最大堆，也就是堆顶的元素是堆中最大的，遍历数组后面元素的时候，
//如果当前元素比堆顶元素大，就把堆顶元素给移除，然后再把当前元素放到堆中，
for (int i = k; i < input.length; ++i) {
if (queue.peek() > input[i]) {
queue.poll();
queue.offer(input[i]);
}
}
//最后再把堆中元素转化为数组
for (int i = 0; i < k; ++i) {
res.add(queue.poll());
}
return res;
}
3，使用TreeMap
原理和堆的原理是一样的，这里就不在叙述
public ArrayList<integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<integer> res = new ArrayList<>(k);
//根据题意要求，如果K>数组的长度，返回一个空的数组
if (k > input.length || k == 0)
return res;
//map中key存放数组中元素，value存放这个元素的个数
TreeMap<integer, integer> map = new TreeMap<>();
int count = 0;
for (int i = 0; i < input.length; i++) {
//map中先存放k个元素，之后map中元素始终维持在k个
if (count < k) {
map.put(input[i], map.getOrDefault(input[i], 0) + 1);
count++;
continue;
}
Map.Entry<integer, integer> entry = map.lastEntry();
//从第k+1个元素开始，每次存放的时候都要和map中最大的那个比较，如果比map中最大的小，
//就把map中最大的给移除，然后把当前元素加入到map中
if (entry.getKey() > input[i]) {
//移除map中最大的元素，如果只有一个直接移除。如果有多个（数组中会有重复的元素），移除一个就行
if (entry.getValue() == 1) {
map.pollLastEntry();
} else {
map.put(entry.getKey(), entry.getValue() - 1);
}
//把当前元素加入到map中
map.put(input[i], map.getOrDefault(input[i], 0) + 1);
}
}
//把map中key存放到集合list中
for (Map.Entry<integer, integer> entry : map.entrySet()) {
int keyCount = entry.getValue();
while (keyCount-- > 0) {
res.add(entry.getKey());
}
}
return res;
}
4，快排
快排的思路就是找到一个中枢值，我们默认第一个，经过一轮比较之后，大于中枢的都在他后面，小于他的都在他前面。然后判断中枢的位置，如果正好等于k，那么他前面的k个元素就是我们要找的。
public ArrayList<integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<integer> res = new ArrayList<>(k);
//根据题意要求，如果K>数组的长度，返回一个空的数组
if (k > input.length || k == 0)
return res;
quickSort(input, res, k, 0, input.length - 1);
return res;
}
private void quickSort(int[] input, ArrayList<integer> res, int k, int left, int right) {
//快排的实现方式有多种，我们选择了其中的一种
int start = left;
int end = right;
while (left < right) {
while (left < right && input[right] >= input[start]) {
right--;
}
while (left < right && input[left] <= input[start]) {
left++;
}
swap(input, left, right);
}
swap(input, left, start);
//注意这里，start是数组中元素的下标。在start之前的元素都是比start指向的元素小，
//后面的都是比他大。如果k==start，正好start之前的k个元素是我们要找的，也就是
//数组中最小的k个，如果k>start，说明前k个元素不够，我们还要往后再找找。如果
//k<start，说明前k个足够了，我们只需要在start之前找k个即可。 if (left> k) {
quickSort(input, res, k, start, left - 1);
} else if (left < k) {
quickSort(input, res, k, left + 1, end);
} else {
//取前面的k个即可
for (int m = 0; m < k; ++m) {
res.add(input[m]);
}
}
}
private void swap(int[] arr, int i, int j) {
if (i == j)
return;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
京公网安备 11010502036488号