最小的K个数

1.

    public static void quickSort(int[] a,int low,int high){
        if (low >= high) {
            return;
        }
        int i=low,j=high;
        int temp=a[i];
        while(i<j) {
            while (i < j && a[j] > temp) {
                j--;
            }
            a[i] = a[j];
            while (i < j && a[i] < temp) {
                i++;
            }
            a[j] = a[i];
        }
        a[i]=temp;
        quickSort(a,low,i-1);
        quickSort(a,i+1,high);
    }

2.

3.

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res=new ArrayList<Integer>();
        if(k>input.length||input.length==0||k<=0){//k<=0防止while死循环
            return res;
        }
        int start=0;
        int end=input.length-1;
        int index=partition(input,start,end);
        while(index!=(k-1)){
            if(index>k-1){
                end=index-1;
                index=partition(input,start,end);
            }else{
                start=index+1;
                index=partition(input,start,end);
            }
        }
        for(int i=0;i<k;i++){
            res.add(input[i]);
        }
        return res;
    }
    public  int partition(int[] a,int low,int high) {
        int pivot = a[low];
        while (low < high) {
            while (low < high && a[high] > pivot) {
                --high;
            }
            a[low]=a[high];
            while (low < high && a[low] <= pivot) {//这里必须加上=，防止带有重复数的结果
                ++low;
            }
            a[high]=a[low];
        }
        a[low]=pivot;
        return low;
    }
}

4.

常见的Top K问题

修改一下partition函数中的大于小于符号就可以了。

5.

最大堆解法，应对海量数据。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        int length = input.length;
        if (k > length || k == 0) {
            return result;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);//o1.compareTo(o2) 从小到大  反过来 从大到小
            }
        });
        for (int i = 0; i < length; i++) {
            if (maxHeap.size() != k) {
                maxHeap.offer(input[i]);
            } else if (maxHeap.peek() > input[i]) {
                //Integer temp = maxHeap.poll();
                //temp = null;
                maxHeap.poll();
                maxHeap.offer(input[i]);
            }
        }
        for (Integer integer : maxHeap) {
            result.add(integer);
        }
        return result;
    }
}