剑指offer - 最小的k个数

题目

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

分析

• 思路1

最简单的思路就是把输入的n个整数进行排序，排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度为O(nlogn)

vector<int> GetLeastNumbers(vector<int> input, int k) {
    vector<int> result;

    // 输入数组为空h，或者最小的k个数大于数组中元素个数
    if (input.empty() || k > input.size())
        return result;

    // 数组排序
    sort(input.begin(), input.end());

    // 存储最小的k个数
    for (int i = 0; i < k; i++)
        result.push_back(input[i]);

    return result;
}

• 思路2

基于Partition函数来解决这个问题，时间复杂度为O(n)。如果基于数组的第k个数字来调整，则使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）

// 快速排序
int Partition(vector<int>& input, int begin, int end) {
    int low=begin;
    int high=end;

    int pivot=input[low];
    while(low<high) {
        while(low<high&&pivot<=input[high])
            high--;
        input[low]=input[high];
        while(low<high&&pivot>=input[low])
            low++;
        input[high]=input[low];
    }
    input[low]=pivot;
    return low;
}

vector<int> GetLeastNumbers2(vector<int> input, int k) {
    int length=input.size();
    // 容错处理
    if(length==0||k>length) return vector<int>();
    if(length==k) return input;

    int start=0;
    int end=length-1;
    int index=Partition(input,start,end);
    while(index!=(k-1)){
        if(index>k-1) {
            end=index-1;
            index=Partition(input,start,end);
        } else {
            start=index+1;
            index=Partition(input,start,end);
        }
    }

    // 获取前面k个元素
    vector<int> res(input.begin(), input.begin() + k);

    return res;
}

• 思路3

可以先创建一个大小为k的数据容器来存储最小的k个数字，接下来每次从输入的n个整数中读入一个数。如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中，如果容器中已有k个数字，也就是容器满了，此时不能再插入新的数字而只能替换已有的数字。

找出这已有的k个数中的最大值，然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值。如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，那么就可以抛弃

因此，当容器满了之后，做3件事情：

• 一是在k个整数中找到最大值
• 二是有可能在这个容器中删除最大值
• 三是有可能插入一个新的数字

如果用一棵二叉树来实现这个数据容器，那么能在O(logk)时间内实现这3步操作。因此，对于n个输入数字而言，总的时间效率就是O(nlogk)。

因此可以使用红黑树实现

vector<int> GetLeastNumbers3(const vector<int> data, int k) {
    // 容错处理
    if (k < 1 || data.size() < k)
        return vector<int>();

    // 仿函数中的greater<T>模板，从大到小排序
    multiset<int, greater<int>> leastNumbers;
    // 得到
    vector<int>::const_iterator iter = data.begin();
    // 遍历数据源
    for (; iter != data.end(); ++iter) {
        if (leastNumbers.size() < k) { // 容器小于k个数就添加
            leastNumbers.insert(*iter);
        } else {
            // 第一个元素是最大值
            multiset<int, greater<int> >::iterator iterGreatest = leastNumbers.begin();
            // 比较两个值
            if (*iter < *(leastNumbers.begin())) {
                leastNumbers.erase(iterGreatest); // 删除元素
                leastNumbers.insert(*iter); // 插入元素
            }
        }
    }

    return vector<int>(leastNumbers.begin(), leastNumbers.end());
}

• 思路4

使用最大堆实现，时间效率是O(nlogk)

vector<int> GetLeastNumbers4(vector<int> input, int k) {
    int length=input.size();
    if(length<=0||k>length) return vector<int>();

    // 得到前面k个数
    vector<int> res(input.begin(),input.begin()+k);
    // 建堆
    make_heap(res.begin(),res.end());
    // 开始遍历
    for(int i=k;i<length;i++) {
        if(input[i]<res[0]) {
            // 先pop,然后在容器中删除
            pop_heap(res.begin(),res.end());
            res.pop_back();

            // 先在容器中加入，再push
            res.push_back(input[i]);
            push_heap(res.begin(),res.end());
        }
    }
    // 使其从小到大输出
    sort_heap(res.begin(),res.end());

    return res;
}

参考

《剑指offer》
最小的k个数