编程实现求最小的K个数

题意

---

题目描述

输入n个整数，找出其中最小的k个数。

例如输入4,5,1,6,2,7,3,8这8个数字，
则最小的4个数字是1,2,3,4,。

分析

---

方法一–排序

---

要求一个序列中最小的k个数，按照惯有的思维方式，很简单，先对这个序列从小到大排序，然后输出前面的最小的k个数即可；

至于选取什么样的排序方法，第一时间应该想到的是快速排序，我们知道，快速排序平均时间复杂度为o(nlogn)，然后再遍历序列中前k个元素输出，即可，总的时间复杂度为o(nlogn + k) = o(nlogn)；——方法一

方法二–选择或者交换排序

---

再进一步想想，题目并没有要求要查找的k个数，甚至是后面的n-k个数是有序的，既然这样，咱们又何必对所有的n个数都进行排序呢？
这个时候，想到了选择或交换排序，即遍历n个数，先把最先遍历到的k个数存入大小为k的数组之中，对这k个数，利用选择或交换排序，找到k个数中的最大数kmax(kmax为这k个元素的数组中最大的元素)，用时间为o(k)（你应该知道，插入或选择排序查找操作需要o(k)的时间），后再继续遍历后n-k个数，x与kmax比较：如果x< kmax，则x代替kmax，并再次重新找出k个元素的数组中的最大元素kmax’；如果x>kmax，则不更新数组。这样每次更新和不更新数组所用的时间为o(k)或o(0)，整趟下来，总的时间复杂度平均下来为：n*o(k) = o(n*k)；——方法二

方法三–最小堆

---

当然，更好的办法是维护k个元素的最大堆，原理与上述第2个方案一致，即用容量为k的最大堆存储最先遍历的k个数，并假设它们即是最小的k个数，建堆需要o(k)后，有k1）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，x），否则不更新堆。这样下来，总费时o(k+(n-k)*logk) = o(nlogk)。此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然，就如上述思路2所述：直接用数组也可以找出前k个小的元素，用时o(n*k)）；

方法四–快速排序的分治划分（中位数作为枢轴）

---

按之美第141页上解法二的所述，类似快速排序的划分方法，n个数存储在数组s中，再从数组中随机选取一个数x（随机选取枢纽元，可做到线性期望时间o(n)的复杂度），把数组划分为sa和sb两部分，sa<= x <=sb，如果要查找的k个小的元素小于sa中的元素个数，则返回sa中较小的k个元素，否则返回sa中k个小的元素 + sb中小的k-|sa|个元素。像上述过程一样，这个运用类似快速排序的partition的快速选择select算法寻找最小的k个元素，在最坏的情况下亦能做到o(n)的复杂度。

不过值得一提的是，这个快速选择select算法是选择数组中“中位数的中位数”作为枢纽元，而非随机选择枢纽元；

方法五–快速排序的分治划分（随机枢轴）

---

randomized-select，每次都是随机选择数列中的一个元素作为主元，在o(n)的时间内找到第k小的元素，然后遍历输出前面的k个小的元素。如果能的话，那么总的时间复杂度为线性期望时间：o(n+k) = o(n)（当n比较小时）；

方法六–线性排序

---

线性时间的排序，即计数排序，时间复杂度虽能达到o(n)，但是，限制条件太多了，不常用；

方法七–最小堆与优先队列

---

”可以用最小堆初始化数组，然后取这个优先队列前k个值。复杂度为o(n)+k*o(logn)“。意思是针对整个数组序列建立最小堆，建堆所用时间为o(n)，然后取堆中的前k个数，即总的时间复杂度为：o(n+k*logn)。

方法八–提取最小堆的元素

---

与上述思路7类似，不同的是在对元素数组原地建立最小堆o(n)后，然后提取k次，但是每次提取时，换到顶部的元素只需要下移顶多k次就足够了，下移次数逐次减少（而上述思路7每次提取都需要logn，所有提取k次，思路7需要k*logn，而本思路8只需要k^2）；

代码

---

#include 
#include 
#include 
#include 
using namespace std;

//  调试开关
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain

class solution
{
protected:
    vector m_res;
public:

    vector getleastnumbers_solution(vector numbers, int k)
    {
        m_res.clear( );

        if(numbers.size( ) == 0 || numbers.size() < k)
        {
            return m_res;
        }
//        m_res.clear( );
//        leastknumbers_bysort(numbers, k);
//
//        m_res.clear( );
//        leastknumbers_byselectsort(numbers, k);
//
//        m_res.clear( );
//        leastknumbers_bybubblesort(numbers, k);


        leastknumbers_bycountsort(numbers, k);


        return m_res;
    }

    ///  排序后输出前k个数字
    vector leastknumbers_bysort(vector numbers, int k)
    {
        debug < res;

        sort(numbers.begin( ), numbers.end( ));
        for(int i = 0; i < k; i++)
        {
            debug < leastknumbers_byselectsort(vector numbers, int k)
    {
        debug < leastknumbers_bycountsort(vector numbers, int k)
    {
        int i, count;
        int num[1000];
        memset(num, '\0', 1000);

        for(i = 0; i < numbers.size( ); i++)
        {
            num[numbers[i]]++;
            debug < getleastnumbers_byfindkth(vector numbers, int k)
    {
        int kth;
        vector res;

        for(int i = 0; i < k; i++)
        {
            kth = findkth(numbers, 0, numbers.size( ) - 1, i);

            debug < &numbers, int left, int right)
    {
        int i = left, j = right;

        ///  我们选择第一个元素作为基准
        ///  这个也可以随机选择
        int pivotindex = left, pivotnum = numbers[pivotindex];

        ddebug <<"pivotnum = " <= pivotnum)
            {
                ddebug <<"[" <= " < numbers, int num)
    {
        int count = 0;
        for(int i = 0; i < numbers.size( ); i++)
        {
            if(numbers[i] == num)
            {
                count++;
            }
        }
        ddebug <<"num = " < numbers.size( ) / 2)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    class greater_class
    {
    public:

        bool operator()(int a, int b)
        {
            return a > b;
        }
    };


    vector getleastnumbers_solution(vector numbers, int k)
    {
        return leastknumbers_byminheap(numbers, k);
    }

    vector leastknumbers_byminheap(vector numbers, int k)
    {
        vector res;



        if(numbers.size( ) == 0 || numbers.size( ) < k)
        {
            return res;
        }
        make_heap(numbers.begin( ), numbers.end( ), greater_class());

        for(int i = 0; i < k; i++)
        {
            //  最小的元素在栈顶
            debug < vec(arr, arr + 8);

    solution solu;
    solu.getleastnumbers_solution(vec, 4);
    return 0;
}

[0]>