题目：
输入n个数，找出其中最小的k个数(k<=n)。
思路：
思路一：
将n个数排序，输出前k个。时间复杂度为O(nlogn)。当k比较大的时候（比如k>n/2），这种方法是一种不错的方法，但是在k比较小的时候，我们并不关心k位之后的数字的顺序，我们甚至也不关心前k个数字的顺序，这种方法带来了额外的操作，所以很显然时间上还有额外的优化空间。
思路二：
维护一个容量为k最大堆，将n个数入堆，最后堆中剩的k个数字就是最小的k个数。维护堆的时间复杂度为logk，需要将n个数字依次入堆，所以这种方法的时间复杂度为O(nlogk)。
思路三：
在方法二中，维护堆的过程依然可以得到前k个数字的顺序，而我们是不关心前k个数字的顺序的。用什么办法可以把数组分成两部分，而不关心每一部分的顺序呢？
当我们在进行快排的时候，我们每次会选择一个“哨兵”，小于哨兵的放在左边，大于哨兵的放在右边，那么如果哨兵的位置恰好为k，那不就刚好分好了吗？如果哨兵的位置不那么完美怎么办呢？递归进行下一次划分就好了！如果哨兵的位置>k，那么就递归处理左边的部分，否则处理右边的部分。
这种方法被称为“Quick Select”,与快排相比，快排需要每次递归处理两边的区间，而这种方法只处理一边，所以时间复杂度低于快排。利用主定理可以求出时间复杂度为O(n)，在不关心前k个数字顺序时是最高效的算法之一。
代码：
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> ans = new ArrayList<>();
if (k>input.length) {
quickSelect(input,0,input.length-1,k-1);
for (int i = 0;i<k;i++){
ans.add(input[i]);
}
return ans;
}
public void quickSelect(int[] a,int l,int r,int k){
if (l>=r) return;
if (r == l+1){
if (a[l]>a[r]){
swap(a,l,r);
}
return;
}
int i = l;
int j = r+1;
int tmp = 0;
while (i<j){
i++;
while (i<=r&&a[i]<a[l]) i++;
j--;
while (j>l&&a[j]>a[l]) j--;
if (i<j) swap(a,i,j);
}
swap(a,l,j);
if (j == k){
return;
}else if (j>k){
quickSelect(a,l,j-1,k);
}else{
quickSelect(a,j+1,r,k);
}
}
public void swap(int[] a,int x,int y){
int tmp = a[x];a[x] = a[y];a[y] = tmp;
}
}
网友评论