求第K小元素(也即是求最小的K个数)第二篇

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 1.9k | 阅读时长 ≈ 2 分钟

来源：https://www.nowcoder.com/profile/448404/codeBookDetail?submissionId=1505827


　　

基本思想

　　基本思想与上一篇相同、分划函数相同，主函数也是分治思想，不过没有随机取主元。 　　

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class SelectTest2 {

    public int[] GetLeastNumbers_Solution(int[] input, int k) {
        int[] res = new int[k];
        int len=input.length;
        if(len==0||k>len||k==0) return res;
        if(len==k) return input;

        int start=0;
        int end=len-1;
        int j=Partition(input,start,end);
        while(j!=k-1){
            if(j>k-1)
                j=Partition(input,start,j-1); //结合Partition函数，此处应为right=j-1，当K=0时不会发生下标越界
            else
                j=Partition(input,j+1,end); //此处应为left=j+1，因为当K=l.length时，函数直接return input，不会再执行Partition函数，从而不会发生下标越界；
                                            //若此处为left=j，则右递归的主元一直都会是l[j]，会导致此处无尽循环。
        }

        for(int i=0; i<k; i++)
            res[i]=input[i];
        return res;
    }

// 分划函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int Partition(int[] l, int left, int right){
    //前置条件：left<=right
    int i=left, j=right+1; //哨兵位（防止越界）
    do{
        do i++; while(l[i]<l[left]&&i<right);  //从首端向后找到>=l[left]的元素l[i]则停止；或i=right时停止
        do j--; while(l[j]>l[left]); //从末端向前找到<=l[left]的元素l[j]则停止；或当j=left时l[j]=l[left]自动停止

        if(i<j) Swap(l, i, j); //若大元素在小元素的前面则调换二者位置
    }while(i<j); //若未越界则继续查找和调换

    Swap(l, left, j); //调换l[left]和l[j]
    return j;
}
/** 调换两个元素的位置 **/
public static void Swap(int[] l, int i, int j) {
    int temp = l[i];
    l[i] = l[j];
    l[j] = temp;
}

// 测试

1
2
3
4
5
6
7
8
    public static void main(String[] args){
        int[] input = {4,5,1,6,2,7,3,8};
        SelectTest2 s = new SelectTest2();
        int[] res = s.GetLeastNumbers_Solution(input,6);
        System.out.println(Arrays.toString(input));
        System.out.println(Arrays.toString(res));
    } 
}

---------------- The End ----------------
0%