29.最小的K个数

题目描述：

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路分析：

利用快速排序的partition函数，partition函数会在数组中找到一个Key值，然后将小于Key的放到它前面，大于Key的放到它后面，我们只需要判断Key的下标t是否等于K，如果等于K那么返回数组的前K个数，如果小于Key那么我们缩小范围，将数组的low更新为t+1，再进行查找，如果大于K，那么将high更新为t-1。直达K等于t。时间复杂度为O(n).

代码：

import java.util.*;

public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer>res=new ArrayList<>();

        if(input==null||k>input.length)

            return res;

        int low=0;

        int high=input.length-1;

        while(low<high){

            int t=partition(low,high,input);

            if(t>k){

                high=t-1;

            }else if(t<k){

                low=t+1;

            }else{

                break;

            }

        }

        for(int i=0;i<k;i++){

            res.add(input[i]);

        }

        return res;

    }

    public int partition(int low ,int high,int []input){

        int key=input[low];

        while(low<high){

            while(low<high&&input[high]>=key){

                high--;

            }

            input[low]=input[high];

            while(low<high&&input[low]<=key){

                low++;

            }

            input[high]=input[low];

        }

        input[low]=key;

        return low;

    }

}

巴特西

29.最小的K个数

题目描述：

思路分析：

代码：

28.连续子数组的最大和

最新文章

热门文章