剑指Offer-29.最小的K个数(C++/Java)

题目：

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

分析：

最先想到的是将数组升序排列，返回前k个元素。不过排序的话效率可能会较低，我们可以使用优先级队列模拟堆来处理。

模拟一个k个元素的最大堆，当堆内元素个数等于k的时候，新来的元素就要和堆顶元素去比较，如果小于堆顶元素，就删除堆顶元素，将新元素添加进堆中，由于最大堆的堆顶元素是最大元素，我们可以保持堆中元素始终是最小的几个，因为每有新的元素来，都会进行比较，最后堆中的元素便是前k个最小元素了。

吐个槽，这种题最后输出又不需要顺序了，牛客网判题真的迷。

程序：

C++

class Solution {

public:

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {

        if(input.size() ==  || k ==  || k > input.size())

            return res;

        for(int num:input){

            if(q.size() < k)

                q.push(num);

            else{

                if(num < q.top()){

                    q.pop();

                    q.push(num);

                }

            }

        }

        while(!q.empty()){

            res.push_back(q.top());

            q.pop();

        }

        //reverse(res.begin(), res.end());

        return res;

    }

private:

    vector<int> res;

    priority_queue<int> q;

};

Java

import java.util.*;

public class Solution {

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

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

            return res;

        for(int num:input){

            if(queue.size() < k)

                queue.add(num);

            else{

                if(num < queue.peek()){

                    queue.poll();

                    queue.add(num);

                }

            }

        }

        for(Integer i : queue) {

            res.add(i);

        }

        return res;

    }

    static Comparator<Integer> cmp = new Comparator<Integer>() {

        public int compare(Integer e1, Integer e2) {

            return e2 - e1;

        }

    };

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

    private PriorityQueue<Integer> queue = new PriorityQueue<>(cmp);

}

巴特西

剑指Offer-29.最小的K个数(C++/Java)

题目：

分析：

程序：

最新文章

热门文章