求第K个数的问题

求第K个数的问题一道经典的题目。给一堆乱序的数,如果它们从小到大排好,求第k个是多少。假设排列的下标从1开始,而非0开始。

这个问题如此之简单而熟悉,可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少,而且还可以不断演进,成为不同复杂程度的问题。

看到这个问题,脑海里的第一反应是一左一右红蓝两条分支——堆排序或者快排。Java中快排用Arrays.sort就可以了,如果是堆排序需要用到PriorityQueue。 用Arrays.sort写起来最简单(这里的参数校验都省掉了):

public int getKth(int[] nums, int k) {
    int[] numsCopy = new int[nums.length];
    System.arraycopy(nums, 0, numsCopy, 0, nums.length);

    Arrays.sort(numsCopy);
    return numsCopy[k - 1];
}

我拷贝了一下数组,以免对原数组做修改。 当然用PriorityQueue写起来不麻烦:

public int getKth(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<>();
    for (int i=0; i<nums.length; i++) {
        heap.add(nums[i]);
    }

    int result = 0;
    for (int i=0; i<k; i++)
        result = heap.poll();

    return result;
}

第一个相关问题来了,Arrays.sort是怎么实现的,复杂度到底是多少?

我们可以简单地认为Arrays.sort是n*log(n)的复杂度。事实上Java的实现用的不是普通的快排,而是DualPivotQuicksort,一个优化了的快速排序算法。一般的快排都是使用一个pivot,每个周期把比它小的元素扔左边,比它大的扔右边。但是DualPivotQuicksort使用了两个pivot,这样原来这堆数就分要分成三份了。在当今多数的计算机条件下,CPU计算速度原来越快,而原本被忽略的内存地址访问速度却很难有一样幅度的提高,因而显得越来越举足轻重。因此我们不能只考虑排序过程中单纯的“大小比较”次数,还需要考虑实际“地址访问”(即num[i])的开销。因为CPU的缓存等原因,在不同情形下,实际对地址访问的次数比算法理论上要少。在有意义的实际应用中,DualPivotQuicksort因为能够在多数情况下减少地址访问次数而最终比原始的快速排序更快。

第二个引申问题来了,只从算法的角度考虑,是否还有优化余地呢?

如果我只需要找到第k个,而不关心从1到k-1之间元素的顺序,也不关心从k+1到最大元素之间的顺序,那能不能通过减少这部分的多余比较,来减少一点运算时间开销呢? 其实是可以的。和上面一样,根据堆排序和快排两种思路来梳理优化方法。 先考虑堆排序。我可以修改原来的最小堆实现,由最小堆改为固定堆大小的最大堆。每次放入元素以后检查堆的大小,确保保持在k。

public int getKth(int[] nums, int k) {
    Queue<Integer> heap = new PriorityQueue<Integer>(k, (o1,o2) -> o2-o1);
    for (int i=0; i<nums.length; i++) {
        heap.add(nums[i]);
        if (i > k - 1)
            heap.poll();
    }

    return heap.poll();
}

注意我初始化的时候初始化了一个大小为k的堆,而实际上我维护着的大小是k-1,这其中有一个留了一个大小为1的缓冲,是因为我都是先放进元素,再poll来调整堆的大小。因此引入这个缓冲以避免不必要的堆大小grow。 再考虑快排优化的思路,每个周期内都把比pivot小的往左边扔,比pivot大的往右边扔,而这样操作一次以后,我可以知道pivot在最后序列中的位置。如果正好是k,那皆大欢喜;如果比k大,说明要找的k在这个pivot的左边,那就再k左边继续进行这样的运算;如果比k小,那就再k右边继续这样的运算。简单来说就是包含两步:

  1. search:找pivot的位置,然后根据和k的比较进一步递归pivot的左边或者是右边的子数组;
  2. partition:把小的数扔pivot左边和把大的数扔pivot右边的过程。

细化来说,上述第二步这个和pivot比较并且往左或者往右扔数的逻辑是:

  • 先把当前最左边的那个数选举出来作为pivot(选pivot的办法有很多,这只是最简单的一个办法),这里的pivot变量实际存储的是它的位置(下标),而其值用变量x存储;
  • 然后指针cur往右走,如果发现有比pivot更小的元素,和pivot交换一下,这样操作直到最后;
  • 再把最左边那个数和pivot最终应该呆的位置上的数交换一下,就使得pivot左边的数都小于pivot上的数,pivot右边的数都大于pivot上的数了。
public int getKth(int[] nums, int k) {
    int[] numsCopy = new int[nums.length];
    System.arraycopy(nums, 0, numsCopy, 0, nums.length);

    return search(numsCopy, k - 1, 0, nums.length - 1);
}

private int search(int[] nums, int k, int left, int right) {
    if (left >= right)
        return nums[left];

    int idx = partition(nums, left, right);
    if (idx == k)
        return nums[idx];
    if (idx < k)
        return search(nums, k, idx + 1, right);
    else
        return search(nums, k, left, idx - 1);
}

private int partition(int[] nums, int left, int right) {
    int x = nums[left];
    int pivot = left;
    int cur = left + 1;
    while (cur <= right) {
        if (nums[cur] < x) {
            pivot++;
            swap(nums, pivot, cur);
        }

        cur++;
    }

    swap(nums, left, pivot);

    return pivot;

}

private void swap(int[] nums, int left, int right) {
    if (left == right)
        return;

    nums[left] ^= nums[right];
    nums[right] ^= nums[left];
    nums[left] ^= nums[right];
}

下面再回到最原始的解法,看堆这个分支。如果这堆数很多,但是k很小,那使用堆为了取第k个数,却需要维护一个巨大的堆,多少显得浪费。于是引出了下面这个问题:

能够改进上面堆排序的做法,仅仅维护一个大小为k的堆吗?

上面的做法为什么不行?因为堆,或者说优先级队列,只有一个出口。换言之,这个最小堆只能每次去poll最小值,如果这个堆的大小已经超过了k,我要是想从中去掉一个肯定不需要的最大值,是没有办法做到的。

但是什么队列有两个出口呢?Deque。可是一般的Deque却又不具备堆的特性,那有没有可能将PriorityQueue和Deque结合起来呢?这样我的问题就解决了。如果需要我自己实现,那我可以分别创建一个最大堆和一个最小堆,分别保存堆元素的引用。代码就不贴了,有上面这些基础,这个很容易实现。

不过开源已经有这样的东西了,有不同的实现版本,有的就叫做PriorityDeque;还有一个版本,是大名鼎鼎的Guava实现的,叫做MinMaxPriorityQueue

如果这堆数不是放在一起,而是在若干个数组里呢?

前面说了,如果这堆数只在一个数组里,有两种办法可以排序,如果是在若干个不同的数组里呢?一样可以从快排和堆排序两个思路去分析。

如果利用上面改进后的快排,一种方法是合并成一个大数组快排,另一种方法是给每个数组快排之后都各自取最大的k个,拿出来放到一起继续快排。

但是倘若k相对比较小可以接受而某一个数组太大,而且数组太多(假设下面的nums.length ≥ k),那么堆排序就更有优势,因为不需要合并,堆的大小只和这个k有关,和这些数组本身大小无关。具体做法是,如果每个数组都还无序,就先给每个数组排序,如果数组很大,不需要完全有序,只需要用上面的优化了的方法各自整理出容量为k的最小堆,从而使得每个数组都有一个最小堆相对应,能够不断pull出当时该数组最小的元素。于是这个问题就变成了,如何从若干个size为k的最小堆中,找出排第k的元素:

先定义这样一个元素。其中idx就存放着第几个堆(下标),num为实际存放的数值:

class Item {
    int num;
    int idx;

    public Item(int num, int idx) {
        this.num = num;
        this.idx = idx;
    }
}

再在主方法中,对整体维护一个最小堆heap,每次从这个堆中取出一个元素的时候,要观察这个元素是从哪里来的,如果是从nums[i]来的,就再从nums[i]取一个当时的最小元素补充到这个heap中。

public int getKth(Queue<Integer> nums[], int k) {
    Queue<Item> heap = new PriorityQueue<>(nums.length, (o1, o2) -> o1.num - o2.num);
    for (int i=0; i<k; i++)
        heap.add(new Item(nums[i].poll(), i));

    Item item = null;
    for (int i=0; i<k-1; i++) {
        item = heap.poll();
        heap.add(new Item(nums[item.idx].poll(), item.idx));
    }

    return heap.poll().num;
}

这个方法其实还有一个有趣的推广,就是从一维到二维,甚至更高维。

具体来说,如果拿到若干个数组,从中任意取两个数x和y,要求x+y的各种组合里面的第k个,或者在全为非负数的情况下引入乘法,比如x*y+2x的所有组合里面的第k个。这样的问题还是可以基于堆来解决,当然,首先要给每个数组各自排序。思路是类似的。

继续,如果这些数在不同的机器上(文件里)呢?

我想这也是个经典问题,这个问题都问烂了。数据量如果放在一台机器上不合适,那么很多人都会想到,可以map-reduce啊,每台机器上进行map运算都求出最大的k个,然后汇总到一台机器上去reduce求出最终的第k个(如果机器很多,这个汇总过程可以是多级汇总)。

可是,这个回答无意之中假定了一个条件,让问题变得好处理很多。这个条件就是——k不大。

假如这堆数很多,因此放在若干台机器上,但是如果这个k也非常大呢?即便要想把这k个数放到一台机器上去找也不可行。

这时候问题就有点复杂了,也有不同的处理方法。一种办法是,通过某种排序方法(比如基于不断归并的外排序),给每台机器上的数据都排好序,然后从中找一个(猜一个可能为所求的数)数作为pivot,并且在每台机器上这些有序数里面都明确这个pivot的位置。假设machine[i]表示第i台机器上,pivot这个数所处的序列,那么把这些machine[i]累加起来,得到的数sum去和k比较:

  • 如果sum==k,那这个数就找到了;
  • 如果sum<k,说明这个数在每台机器上machine[i]往后,直到结尾的这一段数中;
  • 如果sum>k,说明这个数在每台机器上machine[i]往前,直到开头的这一段数中。

如是递归求解。

当然这个方法依然有许多地方可以改进,比如这个预先进行的外排序,未必要完全进行,是可以通过稳重介绍的理论优化掉或者部分优化掉的。

这个方法改变了思考的角度,原本是从一堆数中去找第k个数,现在是从中拿出一个数来,去这堆数中找它应该在的位置。

还蛮有趣的。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

2 comments

  1. Xin v31.1.1 说道:

    补充一下,Arrays.sort当数组个数小于某个值的时候用的是插入排序,所以DualPivotQuicksort有个适用范围

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: