【数据结构与算法面试题】查找最小的k个数

缺乏、安全感 2022-10-07 03:53 162阅读 0赞

> 题目来源“[数据结构与算法面试题80道][80]”。  
> ![这里写图片描述][512c27f65c62bf720a2fef21c0bd668b.png]

问题分析：这是一道比较经典的题目，查找最小的k个元素，最简单的方法就是对这n个整数排序，排序完成后，直接输出前k个最小的元素。那么最快的排序方法是快速排序，其算法的时间复杂度为O(nlogn)。是否还存在比这个更快的方法呢？

方法一：利用快速排序的思想，时间复杂度为O(n)

按照某个点将数组划分成左右两部分，左边的数都小于该划分节点，右边的数都大于该划分节点。如果最终该划分节点的位置小于k-1，则在右边节点中继续划分；如果最终该划分节点的位置大于k-1，则在左边节点中继续划分。这个过程直到最终的划分节点的位置正好为k-1。

int swap(int *a, int start, int end, int point_index){
        int par_point = a[point_index];
        while (start < end){
            if (a[start] >= par_point && a[end] <= par_point){
                int tmp = a[start];
                a[start] = a[end];
                a[end] = tmp;
                start ++;
                end --;
            }else if(a[start] < par_point){
                start ++;
            }else{
                end --;
            }
        }
        return start;
    }
    
    void get_min_k(int *a, int length, int k){
        if (k > length || NULL == a || length <= 0) return;
    
        int new_index = swap(a, 0, length-1, k);
        while (true){
            if (new_index == k) break;
            else if (new_index > k){
                new_index = swap(a, 0, new_index, k);
            }else{
                new_index = swap(a, new_index, length-1, k);
            }
        }
    }

方法二：利用堆排序，时间复杂度为O(nlogk)

上述方法的缺点是其对数组进行了修改，在堆排序中，可采用小顶堆，其中堆的大小为k，若此时堆的大小小于k时，则将数插入堆中；若此时堆中的大小大于等于k，则比较堆中最大的整数与待插入整数的大小，插入较小的整数。

void get_min_k(int *a, int length, int k, set<int> &s){
        if (k > length || NULL == a || length <= 0) return;
    
        for (int i = 0; i < length; i++){
            if (s.size() < k){
                s.insert(a[i]);
            }else{
                set<int>::iterator it = --s.end();
                if (a[i] < *it){
                    s.erase(*it);
                    s.insert(a[i]);
                }
            }
        }
    }

[80]: https://yq.aliyun.com/articles/40478?utm_content=m_15768
[512c27f65c62bf720a2fef21c0bd668b.png]: /images/20221005/09779e235454413d82121e7fca9fd053.png