leetcode 链接：最小的k个数

题目

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

示例：

  1. 输入：arr = [3,2,1], k = 2
  2. 输出：[1,2] 或者 [2,1]
输入：arr = [0,1,2,1], k = 1
输出：[0]

解答 & 代码

解法一：堆排序（小根堆）

建立小根堆后，进行 k 次交换调整，数组的最后 k 个元素就是最小的 k 个数（不用进行完整的排序）

class Solution {
private:
    void adjustHeap(vector<int>& arr, int start, int end)
    {
        int dadIdx = start;
        int sonIdx = start * 2 + 1;
        while(sonIdx <= end)
        {
            if(sonIdx + 1 <= end && arr[sonIdx + 1] < arr[sonIdx])
                sonIdx = sonIdx + 1;
            if(arr[sonIdx] < arr[dadIdx])
            {
                swap(arr[sonIdx], arr[dadIdx]);
                dadIdx = sonIdx;
                sonIdx = dadIdx * 2 + 1;
            }
            else
                return;
        }
    }

    void minHeap(vector<int>& arr, int k)
    {
        int len = arr.size();
        for(int i = len / 2 - 1; i >= 0; --i)
            adjustHeap(arr, i, len - 1);

        swap(arr[0], arr[len - 1]);
        for(int i = 1; i < k; ++i)
        {
            adjustHeap(arr, 0, len - i - 1);
            swap(arr[0], arr[len - i - 1]);
        }
    }
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int len = arr.size();
        minHeap(arr, k);
        vector<int> result(k, 0);
        for(int i = 0; i < k; ++i)
            result[i] = arr[len - i -1];
        return result;
    }
};

执行结果：

执行结果：通过

执行用时：32 ms, 在所有 C++ 提交中击败了 71.73% 的用户
内存消耗：18.3 MB, 在所有 C++ 提交中击败了 79.10% 的用户

解法二：堆排序（大根堆）

解法一建立小根堆，需要对数组中所有元素建立堆，再取 k 次堆顶，得到 k 个最小的数。
实际上，一般取最小的 k 个数使用大根堆，只需要先将数组的前 k 个数建立大根堆，再依次将数组中剩余元素与大根堆堆顶元素比较，如果小于堆顶元素，则与堆顶交换，并调整大根堆。最终前 k 个数就是最小的 k 个数

class Solution {
private:
    void adjustHeap(vector<int>& arr, int start, int end)
    {
        int dadIdx = start;
        int sonIdx = start * 2 + 1;
        while(sonIdx <= end)
        {
            if(sonIdx + 1 <= end && arr[sonIdx + 1] > arr[sonIdx])
                sonIdx = sonIdx + 1;
            if(arr[sonIdx] > arr[dadIdx])
            {
                swap(arr[sonIdx], arr[dadIdx]);
                dadIdx = sonIdx;
                sonIdx = dadIdx * 2 + 1;
            }
            else
                return;
        }
    }

    void maxHeap(vector<int>& arr, int k)
    {
        int len = arr.size();
        for(int i = k / 2 - 1; i >= 0; --i)
            adjustHeap(arr, i, k - 1);
    }
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int len = arr.size();
        maxHeap(arr, k);                    // 将前 k 个数建立大根堆
        for(int i = k; i < len; ++i)        // 将剩下的数依次与堆顶元素比较
        {
            if(arr[i] < arr[0])                // 如果当前元素的值小于堆顶元素
            {
                swap(arr[0], arr[i]);        // 则将当前元素与堆顶元素交换
                adjustHeap(arr, 0, k - 1);    // 调整堆
            }
        }

        vector<int> result(k, 0);
        for(int i = 0; i < k; ++i)            // 最终前 k 个数就是最小的 k 个数
            result[i] = arr[i];
        return result;
    }
};

执行结果：

执行结果：通过

执行用时：24 ms, 在所有 C++ 提交中击败了 95.06% 的用户
内存消耗：18.3 MB, 在所有 C++ 提交中击败了 71.13% 的用户

解法三：快排

快排，不用完整排序，如果分割点 pivot == k - 1，说明当前数组前面 k 个就是最小的 k 个数，虽然这 k 个数的顺序不能保证，但也符合题目要求

class Solution {
private:
    int partition(vector<int>& arr, int start, int end)
    {
        int randomIdx = rand() % (end - start + 1) + start;
        swap(arr[start], arr[randomIdx]);
        int pivot = arr[start];
        int left = start;
        int right = end;
        while(left < right)
        {
            while(left < right && arr[right] >= pivot)
                --right;
            arr[left] = arr[right];
            while(left < right && arr[left] <= pivot)
                ++left;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }

    void quickSort(vector<int>& arr, int start, int end, int k)
    {
        if(start >= end)
            return;
        int pivot = partition(arr, start, end);
        if(pivot == k - 1)
            return;
        quickSort(arr, start, pivot - 1, k);
        quickSort(arr, pivot + 1, end, k);
    }
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int len = arr.size();
        quickSort(arr, 0, len - 1, k);
        vector<int> result(k, 0);
        for(int i = 0; i < k; ++i)
            result[i] = arr[i];
        return result;
    }
};

执行结果：

执行结果：通过

执行用时：36 ms, 在所有 C++ 提交中击败了 54.60% 的用户
内存消耗：18.3 MB, 在所有 C++ 提交中击败了 69.54% 的用户