Skip to content

数组中第 K 个数 快速选择算法

Jump to bottom
小梁同学 edited this page Oct 18, 2019 · 1 revision

背景

快速选择算法常用来解决：在未排序的数组中查找第 K 大数的位置 快速选择算法属于：Partition Array 系列问题中的一种，同时又是快速排序算法的基础，所以这节我们一块看下快速选择算法及其实现

Partition Array

Partition Array 算法是：将数组按照一定的规则对数组中的数据进行分隔 比如我有个数据是: [a, b, c, D, e , C, t]， 而我想得到数据是[a, b, c, e, t, D, C]， 即将数组分隔成小写字母和大写字母；要实现这个分隔字符数组的功能，我们这需要两个指针，一个在数组的开始位置：left，一个在数组的结束位 置：right；它们的含义如下：

  • left: [0, left) 均为小写字母
  • right: (right, array.length - 1] 均为大写 为了满足上面的 left，和 right 的含义，当 left && right 均遇到不满足含义的字符时，需要将 left和 right 指向的内容做交换 代码如下：
int left = 0, right = nums.length - 1;
while (left < right) {
    // 左边的一组
    while (left < nums.length && 当前字符是小写字符) {
        left++;
    }
    // 右边的一组
    while (right >= 0 && 当前字符是大写字符) {
        right--;
    }
    // 当前 left 和 right 分别指向了:
    // 1. left 指向在左边组但不满足左边组条件的元素；
    // 2. right 指向在右边的组单不满足右边组的条件
    // 这个时候需要将 right 和 left 指向的两个元素交换
    if (left < right) { //  注意点
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] =  temp;
    }
}

注意点为什么作交换之前要确保 left < right：

当走到这一步的时候 left 指向一个大写字符，right 指向一个小写字符，而数据是已经分隔好的话，left 和 right 分别指向第一个大写字符，和最后一个小写字符， 对于数据[a, b, c, e, t, D, C] 来说left 指向 D，right 指向 t，此时如果交互就发生了错误

快速选择

快速选择算法如何快速地从数组中查找第 K 个最大的数？

对于一个未排序的数组来说，我任取其中的一个数 Tag，将小于该数的数字放置到该数字的左边，大于该数字的放置到该数字的右边，此时 Tag 的位置就是当整个数组排好序之后的位置：

原数组选取 5 作为 Tag：[4, 5, 2, 7, 8] 对 Tag 进行 PartitionArray：[4, 2, 5, 7, 8]，规则是：小于 Tag 的值放到 Tag 左边，大于 Tag 的值放到右边 原数组拍好序结果：[2, 4, 5, 7, 8]

我们可以看到Tag 的位置在 PartitionArray 后就可以确定下来

对与一个有序数组来说，第 K 个最大的数就是：从大到小排列完成后，第 K 个数

快速选择查找第 K 个最大数，具体的实现步骤可以这样：

  1. 从数组中任取一个数 a，按照前面说的：将大于 a 的数放置在 a 的左侧，小于 a 的数放在右侧，那么此时 a 的位置就是整个数组排序后 a 的位置。
  2. a 是不是第 K 个数？如果它的位置大于 K 说明它小于第 K 个数，那么第 K 个数应该在左边，反之它的位置小于 K 说明它大于第 K 个数，那么第 K 个数应该在右边
  3. 根据 步骤2. 选择左边或者右边，继续步骤1.
public int findKthLargest(int[] nums, int k) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int position = quickSelect(nums, left, right);
        // 步骤2，根据 position 与 K 的位置选择一边
        if (position > k - 1) {
            right = position - 1;
        } else if (position < k - 1){
            left = position + 1;
        } else {
            return nums[position];
        }
    }
    return nums[k - 1];
}
// 步骤1. 选择数组第一个元素，分割数组
private int quickSelect(int[] nums, int left, int right) {
    int start = left;
    int point = nums[left];
    /// 左边的元素 大于等于 point
    /// 右边的元素 小于 point
    left += 1;
    while (left < right) {
        while (left < nums.length && nums[left] >= point) {
            left++;
        }
        while (right >= 0 && nums[right] < point) {
            right--;
        }
        if (left < right) {
            swipe(nums, left, right);
        }
    }
    // 结束循环后，right 可能指向大于 point 的元素，
    // 如果满足这个条件，那么 right 的位置就是 point 应该在的位置
    if (nums[right] > point) {
        swipe(nums, start, right);
    }
    return right;
}

如果进入 while 循环，那么while 结束后，right 指向的最后一个 >= Tag 的位置，left 指向第一个 < Tag 的位置。 如果没有进入 while 循环，说明数据中就两个2，这个时候需要判断下最后一个是否是大于第一个数 ✅

总结

快速选择算法适用于静态数据即给定一个数组从数组中找出第 K 个数，但是对于给定一个数据流来说，快速选择算法无法解决，因为 PartitionArray 的时候数据是会发生变化的。对于数据流的数据来说，选择第 K 个数可以使用堆去实现。

Clone this wiki locally