图文详解 | #牛的体重排序#
牛的体重排序
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);
}
}
};
美团公司福利 1402人发布
查看16道真题和解析