剑指Offer 最小的k个数

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

本题在《剑指offer》中提供了两种解题思路，分别是使用快速排序和使用红黑树，下面分别讨论：

第一种：使用快速排序的方法

由于我们使用快速排序可以得到第n个位置的数字，并且n左边的数字比n小，n右边的数字比n大，那么如果n=k+1，则将n左边的数字返回即可，这里返回的K个数字没有排序，会改变输入的数组，时间复杂度为O(n)，代码如下：

class Solution {
private:
    vector<int> v;
    int kk;
public:
    int Partition(vector<int> &input, int start, int end) {
        // 快速排序中交换的方法
        //if (input.empty() || start>end) return -1;
        swap(input[start], input[end]);
        
        int small = start - 1;
        for (int i = start; i < end; i++) {
            if (input[i] < input[end]) {
                small++;
                if (i != small) {
                    swap(input[i], input[small]);
                }
            }
        }
        small++;
        swap(input[small], input[end]);
        return small;
    }
    vector<int> getResult(vector<int> &input, int start, int end) {
        int index = Partition(input, start, end);
        // 看下找到的数是不是第k个，如果是，则把前面的k个数字返回
        while (index != kk - 1) {
            if (index < kk - 1) {
                start = index + 1;
                index = Partition(input, start, end);
            }
            else {
                end = index - 1;
                index = Partition(input, start, end);
            }
        }
        for (int i = 0; i < kk; i++) {
            v.push_back(input[i]);
        }
        return v;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        kk = k;
        if (input.empty() || k>input.size() || k <= 0) return v;
        vector<int> result = getResult(input, 0, input.size() - 1);
        return result;
 
    }
};

第二种，利用红黑树、桶排序，时间复杂度为 O(nlogK)，适合海量数据

具体思路为，首先建立一个容器，该容器大小为k，然后遍历整个数组，如果容器没满，则添加进去一个数字，如果容器满了，则用容器里的最大的数字和该遍历的数组中的数字x比较，如果x大于这个容器中最大的值，则说明x不是最小的k个数字，否则如果x小于容器中的最大值，把容器中的最大值去掉，添加进x值。容易想到的是使用最大堆，或者红黑树。这里用multiset存储，因为它本身就是基于红黑树实现的。代码如下：

class Solution {
private:
    vector<int> result;
    multiset<int, greater<int> >sets;
 
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        sets.clear();
        result.clear();
        if (input.empty() || k<0 || k>input.size()) return result;
        for (vector<int>::iterator iter = input.begin(); iter != input.end(); iter++) {
            if (sets.size() < k ) {
                sets.insert(*iter);
            }
            else {
                if (*iter < *sets.begin()) {
                    sets.erase(sets.begin());
                    sets.insert(*iter);
                }
            }
        }
        for (multiset<int, greater<int> >::iterator iter = sets.begin(); iter != sets.end(); iter++) {
            result.push_back(*iter);
        }
         
        return result;
    }
};