剑指 Offer 40. 最小的k个数

法一

我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中,随后从第 k+1 个数开始遍历,如果当前遍历到的数比大根堆的堆顶的数要小,就把堆顶的数弹出,再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> arr, int k) {
        priority_queue<int> heap;
        for (int i = 0; i < arr.size(); i++) {
            if (heap.size() < k) heap.push(arr[i]);
            else if (heap.size() && heap.top() > arr[i]) {
                heap.pop();
                heap.push(arr[i]);
            }
        }

        vector<int> res;
        while (heap.size()) {
            res.push_back(heap.top());
            heap.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

法二

我们可以借鉴快速排序的思想。我们知道快排的划分函数每次执行完后都能将数组分成两个部分,小于等于分界值 pivot 的元素的都会被放到数组的左边,大于的都会被放到数组的右边,然后返回分界值的下标。与快速排序不同的是,快速排序会根据分界值的下标递归处理划分的两侧,而这里我们只处理划分的一边。

我们定义函数 quickSelected(arr, l, r, k) 表示划分数组 arr 的 [l,r] 部分,使前 k 小的数在数组的左侧,在函数里我们调用快排的划分函数,假设划分函数返回的下标是 pos(表示分界值 pivot 最终在数组中的位置),即 pivot 是数组中第 pos - l + 1 小的数,那么一共会有三种情况:

  1. 如果 pos - l + 1 == k,表示 pivot 就是第 k 小的数,直接返回即可;
  2. 如果 pos - l + 1 < k,表示第 k 小的数在 pivot 的右侧,因此递归调用 quickSelected(arr, pos + 1, r, k - (pos - l + 1));
  3. 如果 pos - l + 1 > k,表示第 k 小的数在 pivot 的左侧,递归调用 quickSelected(arr, l, pos - 1, k)。

在函数返回后,将前 k 个数放入答案数组返回即可。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        srand(time(0));
        quickSelect(arr, 0, arr.size() - 1, k);
        
        vector<int> res;
        for (int i = 0; i < k; i++)
            res.push_back(arr[i]);
        return res;
    }

    void quickSelect(vector<int> &a, int l, int r, int k) {
        if (l < r) {
            int index = Partition(a, l, r);
            int cnt = index - l + 1;
            if (k == cnt) 
                return;
            else if (k < cnt) 
                quickSelect(a, l, index - 1, k);
            else
                quickSelect(a, index + 1, r, k - cnt);
        }
    }
    
    int Partition(vector<int> &a, int l, int r) {
        int pivot = rand() % (r - l + 1) + l;
        swap(a[pivot], a[r]);
        
        int index = l;
        for (int i = l; i < r; i++) {
            if (a[i] < a[r])
                swap(a[i], a[index++]);
        }
        
        swap(a[index], a[r]);
        return index;
    }
};
上一篇:debug:am dumpheap命令源码分析


下一篇:如何在KEIL中使用MicroLIB