剑值offer：最小的k个数

这是在面试常遇到的topk问题。

题目描述：

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

解题思路：

思路一：用快排对数组做一次排序，输出前k个。这种方法会改变原数组排列，复杂度为O(nlogn)。

思路二：基于partition思想，进行一次快速排序用哨兵数分割数组中的数据。由于partition每次将数组分成两段，左半部分小于关键字，右半部分大于关键字。可以递归做partition，关键字位置，若关键字位置等于k-1，则输出左半部分。否则，若大于k-1，则对左半部分做partition；若小于k-1，则往后拓展一位。

这种方法同样会改变原数组排列，算法复杂度为O(n)。

思路三：大顶二叉堆。基于红黑树（？？？）思想，首先创建一个大小为k的容器，用来存储最小的k个数字；然后每次从输入的n个整数中输入一个数，如果容器中已有的数字少于k个，则直接把读入的整数放入容器；如果容器中已有k个数字，则不能再插入新的数字而只能替换已有的数字。替换的原则：如果待插入的值m比容器中的最大值n小，则m替换n；如果待插入的值m比容器中的最大值n大，则保持不变。（在k个整数中找到最大值、删除容器最大值、插入一个新的数字）

可以用优先队列完成，设定一个大小为k的优先队列，将数组一次放进去，由于优先队列的排列是从大到小，所以每次当新的数进队时，当队列已满，就做出队操作，每次出队的都是最大的元素。因此最后保留在队列当中的就是最小的k个数。算法复杂度O(nlogk)，不会改变原数组的排列。该方法适合处理海量数据。

代码：

思路一：

class Solution {

public:

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

        vector<int> res;

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

            return res;

        if(input.size() < k)

            return res;

        sort(input.begin(), input.end());

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

            res.push_back(input[i]);

        return res;

    }

};

思路二：

class Solution {

public:

    int partition(vector<int>& a, int low, int high) //要改变vector，必须传入地址

    {

        int temp;

        int base = low;

        temp = a[low];

        while(low<high)

        {

            while(a[high] >= temp && low<high)

                high--;

            while(a[low] <= temp && low<high)

                low++;

            if(low<high)

                swap(a[low], a[high]);

        }

        swap(a[base], a[low]);

        return low;

    }

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

        vector<int> res;

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

            return res;

        int low = ;

        int high = input.size()-;

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

        while(index != (k-))

        {

            if(index > (k-))

            {

                high = index-;

                index = partition(input, low, high);

            }

            else

            {

                low = index+;

                index = partition(input, low, high);

            }

        }

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

            res.push_back(input[i]);

        return res;

    }

};

思路三：

class Solution {

public:

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

        vector<int> res;

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

            return res;

        priority_queue<int> q;

        for(int i=; i<input.size(); i++)

        {

            q.push(input[i]);

            if(q.size()>k)

            {

                q.pop();

            }

        }

        while(!q.empty())

        {

            res.push_back(q.top());

            q.pop();

        }

        return res;

    }

};

巴特西

剑值offer：最小的k个数

最新文章

热门文章