一些算法题中要求寻找无序数组的中位数/第k小的数,本文对此作一个小结。

排序

因数据保存在数组,最直观的方法是排序,调用所用的编程语言的标准库里的排序函数,比如c++里的sort(),然后取中位数/第k个数即可。

int getKSmallest(vector<int> &dat, int k) {
    sort(dat.begin(), dat.end());
    return dat[k - 1];
}

时间复杂度一般$O(n\log n)$,空间复杂度 $O(1)$。

快速选择

快速选择算法与快速排序qsort很像,采用的是分而治之的思想。基本思路是:任意挑一个元素,以该元素为支点,将数组分成两部分,左部分是小于等于支点的,右部分是大于支点的。如果你的运气爆棚,左部分正好是$\frac{n-1}{2}$个元素,那么支点的那个数就是中位数。可以看作对快速排序partition的应用。

int getKSmallest(vector<int> &dat, int k) {
    int l = 0, r = dat.size() - 1;
  k--;
  while(l < r) {
    int pivot = dat[l], i = l, j = r;
    while (i < j) {
      while (i < j && dat[j] >= pivot) j--;
        while (i < j && dat[i] <= pivot) i++;
      if (i < j) swap(dat[i], dat[j]);
    } 
    dat[l] = dat[i];
    dat[i] = pivot;
    if (i == k) return dat[k];
    else if (i < k) l = i + 1;
    else r = i - 1;
  }
  return dat[k];
}

时间复杂度$O(n)$,空间复杂度$O(1)$。

大小堆

另一个方法是维护大/小堆。除了手写维护数据结构堆,可以用标准库,例如c++中的priority_queue

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};
/*
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/

练习题

参考

https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/02.01.html

https://www.geekxh.com/1.99.%E5%85%B6%E4%BB%96%E8%A1%A5%E5%85%85%E9%A2%98%E7%9B%AE/22.html

最后修改:2022 年 03 月 03 日
如果觉得我的文章对你有用,请随意赞赏