02-09 15:04 重庆大学 C++

关注

图文详解 | #牛的体重排序#

牛的体重排序

https://www.nowcoder.com/practice/1afd5afef2aa49a8a39b63bb9d2821f9

思路：二分查找

两个数组都是从小到大排好了的，找出中位数，只需要归并成一个从小到大排好的数组，返回中间的数就可以了。但这么做的时间复杂度是O(m+n)，而题目要求的是O(log(m+n))，这就意味着我们甚至不能把数组里的数都看一遍。这和二分查找很像，都是从小到大排好的数组，都是O(log(n))时间复杂度。但这里我们有两个数组，把两个数组都掰成两段后，我们就会得到四段：

我们要找到AB整体的中位数，它在这四个段的哪个段里呢？它应该在AB归并成的数组的中间：

注意到，AB整体被两个中轴分成了三段，并且AB整体的三段跟A的两段、B的两段有关系：

整体的左段来自A的左段和B的左段，整体的中段来自A的右段和B的左段，整体的右段来自A的右段和B的右段。

有些段是不可能存在中位数的，我们可以将这些段排除掉：

一轮轮淘汰，将数组A和数组B分之又分，最终剩下的，就是我们要找的中位数。

以上就是解决该问题的大致思路，如果还想知道更多细节的话，可以继续往下看。

难点：将问题转化成找第k小的数

在总长度是偶数的情况下，找中位数需要找两个数，而这两个数可能都在A，可能都在B，也可能A，B各一个。如果我们写的函数能找任意第k小的数，那就不必这么麻烦分类讨论了。在偶数的情况下，我们可以分两次找，第一次找第size/2小的数，第二次找第size/2 + 1小的数：

double findMedianSortedArrays(vector<int>& weightsA, vector<int>& weightsB) {
        // write code here
        int size = weightsA.size() + weightsB.size();
        if (size & 1) {
			// 奇数情况
            return findKth(size / 2, weightsA, weightsB);
        } else {
			// 偶数情况
            return 0.5 * (findKth(size / 2 - 1, weightsA, weightsB) + findKth(size / 2, weightsA, weightsB);
        }
    }

难点：明确中轴、左段、右段

要二分，要递归，就得弄清楚这些问题：数组中间元素的下标是什么，左段的长度是多少，右段从哪开始，数组的长度如果是偶数又会怎么样？当弄不清楚时，不妨举个例子，画个图，琢磨出明确的定义：

难点：什么时候排除左段？什么时候排除右段？

排除掉第k小的数不可能在的段

比如说，第k小的数位于整体的中段时，就可以把A的左段排除掉，因为A的左段必然在整体的左段，B的右段同理：

但是怎么知道第k小的数位于整体的哪里呢？我们可没有上帝视角，我们不过是观测了数组里的两个数：

我们不确定第k小的数在哪，我们甚至都不知道我们要找的第k小的数会不会刚好是10或11。

但AB整体跟A、B确实是有一些关系的：

整体的左段来自A的左段和B的左段，整体的中段来自A的右段和B的左段，整体的右段来自A的右段和B的右段（不妨设A的中轴比B的中轴更小）。

当k太小或太大时

当k比A左段的长度还小时：

我们可以排除掉A的右段和B的右段，因为这段区间里的数，要么来自A的左段，要么来自B的左段：

同理，当k比A的长度加上B的左段长度还大时：

因为这段区间里的数，要么来自A的右段，要么来自B的右段，所以可以排除掉A的左段和B的左段。

据此，我们可以写出以下代码：

    int findKth(int kth, vector<int>& A, int Abegin, int Asize, vector<int>& B, int Bbegin, int Bsize) {
        int Ahalf = Asize / 2;
        int Bhalf = Bsize / 2;
        if (A[Abegin + Ahalf] <= B[Bbegin + Bhalf]) {
            if (kth < Ahalf) {
				// 排除A的右段和B的右段
                return findKth(kth, A, Abegin, Ahalf, B, Bbegin, Bhalf);
            } else if (Asize + Bhalf <= kth) {
				// 排除A的左段和B的左段
                return findKth(kth - Ahalf - Bhalf, A, Abegin + Ahalf, Asize - Ahalf, B, Bbegin + Bhalf, Bsize - Bhalf);
            }
        } else {
            // B[Bbegin + Bhalf] < A[Abegin + Ahalf]时同理
            return findKth(kth, B, Bbegin, Bsize, A, Abegin, Asize);
        }
    }

好，这样就能排除掉一半的数了，不过如果k不大不小呢？

当k不大不小时

其实只要k在整体的左边，我们就可以排除掉B的右段：

因为B右段里的数去不到那么靠左：

B右段里的数局限在整体的右边：

同理，只要k在整体的右边，我们就可以排除掉A的左段：

因为A左段里的数去不到那么靠右：

A左段里的数局限在整体的左边：

无论k是多少，都可以排除掉一段

综上所述，代码如下：

    int findKth(int kth, vector<int>& A, int Abegin, int Asize, vector<int>& B, int Bbegin, int Bsize) {
        int Ahalf = Asize / 2;
        int Bhalf = Bsize / 2;
        if (A[Abegin + Ahalf] <= B[Bbegin + Bhalf]) {
            if (kth < Ahalf) {
                // 排除A的右段和B的右段
                return findKth(kth, A, Abegin, Ahalf, B, Bbegin, Bhalf);
            } else if (Asize == 1 || kth < Ahalf + Bhalf) {
                // 排除B的右段
                return findKth(kth, A, Abegin, Asize, B, Bbegin, Bhalf);
            } else if (Asize + Bhalf <= kth) {
                // 排除A的左段和B的左段
                return findKth(kth - Ahalf - Bhalf, A, Abegin + Ahalf, Asize - Ahalf, B, Bbegin + Bhalf, Bsize - Bhalf);
            } else {
                // Ahalf + Bhalf <= kth
                // 排除A的左段
                return findKth(kth - Ahalf, A, Abegin + Ahalf, Asize - Ahalf, B, Bbegin, Bsize);
            }
        } else {
            // B[Bbegin + Bhalf] < A[Abegin + Ahalf]时同理
            return findKth(kth, B, Bbegin, Bsize, A, Abegin, Asize);
        }
    }

每轮我们都可以排除掉A的一半或B的一半，因此时间复杂度是O(log(m+n))。

难点：处理边界情况

不断地将数组二分，当数组的长度变成0，或者1时，就分不了了：

如果我们是要二分查找，那么此时我们已经大功告成了。但是我们有两个数组，当A的长度变成1时，B的长度还可能很长，此时我们希望继续对B进行二分。然而当k的取值恰好让我们决定对A继续二分时，我们就有可能会进入死循环：

发生上述情况时，我们不应排除A的左段，而应排除B的右段，不然就什么也排除不了。

再看看当B的长度为1时：

不会导致什么也排除不了，因此可以不管。

综上所述，代码如下：

    int findKth(int kth, vector<int>& A, int Abegin, int Asize, vector<int>& B, int Bbegin, int Bsize) {
        if (Asize == 0)
            return B[Bbegin + kth];
        if (Bsize == 0)
            return A[Abegin + kth];
        if (Asize == 1 && Bsize == 1) {
            if (kth == 0)
                return min(A[Abegin], B[Bbegin]);
            else
                // kth == 1
                return max(A[Abegin], B[Bbegin]);
        }
        int Ahalf = Asize / 2;
        int Bhalf = Bsize / 2;
        if (A[Abegin + Ahalf] <= B[Bbegin + Bhalf]) {
            if (kth < Ahalf) {
                // 排除A的右段和B的右段
                return findKth(kth, A, Abegin, Ahalf, B, Bbegin, Bhalf);
            } else if (kth < Ahalf + Bhalf) {
                // 排除B的右段
                return findKth(kth, A, Abegin, Asize, B, Bbegin, Bhalf);
            } else if (Asize + Bhalf <= kth) {
                // 排除A的左段和B的左段
                return findKth(kth - Ahalf - Bhalf, A, Abegin + Ahalf, Asize - Ahalf, B, Bbegin + Bhalf, Bsize - Bhalf);
            } else {
                // Ahalf + Bhalf <= kth
                if (Asize == 1) {
                    // 排除B的右段
                    return findKth(kth, A, Abegin, Asize, B, Bbegin, Bhalf);
                }
                // 排除A的左段
                return findKth(kth - Ahalf, A, Abegin + Ahalf, Asize - Ahalf, B, Bbegin, Bsize);
            }
        } else {
            // B[Bbegin + Bhalf] < A[Abegin + Ahalf]时同理
            return findKth(kth, B, Bbegin, Bsize, A, Abegin, Asize);
        }
    }

};

最终代码：

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weightsA int整型vector
     * @param weightsB int整型vector
     * @return double浮点型
     */
    double findMedianSortedArrays(vector<int>& weightsA, vector<int>& weightsB) {
        // write code here
        int size = weightsA.size() + weightsB.size();
        if (size & 1) {
            // 奇数情况
            return findKth(size / 2, weightsA, 0, weightsA.size(), weightsB, 0, weightsB.size());
        } else {
            // 偶数情况
            return 0.5 * (findKth(size / 2 - 1, weightsA, 0, weightsA.size(), weightsB, 0, weightsB.size()) + findKth(size / 2, weightsA, 0, weightsA.size(), weightsB, 0, weightsB.size()));
        }
    }

    int findKth(int kth, vector<int>& A, int Abegin, int Asize, vector<int>& B, int Bbegin, int Bsize) {
        if (Asize == 0)
            return B[Bbegin + kth];
        if (Bsize == 0)
            return A[Abegin + kth];
        if (Asize == 1 && Bsize == 1) {
            if (kth == 0)
                return min(A[Abegin], B[Bbegin]);
            else
                // kth == 1
                return max(A[Abegin], B[Bbegin]);
        }
        int Ahalf = Asize / 2;
        int Bhalf = Bsize / 2;
        if (A[Abegin + Ahalf] <= B[Bbegin + Bhalf]) {
            if (kth < Ahalf) {
                // 排除A的右段和B的右段
                return findKth(kth, A, Abegin, Ahalf, B, Bbegin, Bhalf);
            } else if (kth < Ahalf + Bhalf) {
                // 排除B的右段
                return findKth(kth, A, Abegin, Asize, B, Bbegin, Bhalf);
            } else if (Asize + Bhalf <= kth) {
                // 排除A的左段和B的左段
                return findKth(kth - Ahalf - Bhalf, A, Abegin + Ahalf, Asize - Ahalf, B, Bbegin + Bhalf, Bsize - Bhalf);
            } else {
                // Ahalf + Bhalf <= kth
                if (Asize == 1) {
                    // 排除B的右段
                    return findKth(kth, A, Abegin, Asize, B, Bbegin, Bhalf);
                }
                // 排除A的左段
                return findKth(kth - Ahalf, A, Abegin + Ahalf, Asize - Ahalf, B, Bbegin, Bsize);
            }
        } else {
            // B[Bbegin + Bhalf] < A[Abegin + Ahalf]时同理
            return findKth(kth, B, Bbegin, Bsize, A, Abegin, Asize);
        }
    }

};