本文主要是介绍LeetCode 小水题选做，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

LeetCode 小水题选做

• LeetCode 小水题选做
  • 4. 寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数

题目链接

题目大意：

给定两个排好序的数组 \(a, b\)，长度分别为 \(n, m\)。设 \(c\) 为把 \(a\)、\(b\) 合并后再排好序的数组，求 \(c\) 的中位数。要求时间复杂度 \(\mathcal{O}(\log(n + m))\)（不计输入）。

一、初步转化：如何避免关于中位数的繁杂分类讨论

记两个有序数列（nums1, nums2）分别为 \(a, b\)。

首先，根据 \(n + m\) 的奇偶性不同，中位数的定义略有不同。考虑将所有 \(n + m\) 个数放在一起，排好序，记为数列 \(c\)。则当 \(n + m\) 为奇数时，中位数是 \(c\) 里第 \(\lfloor\frac{n + m}{2}\rfloor + 1\) 个数；当 \(n + m\) 为偶数时，中位数是 \(c\) 里第 \(\frac{n + m}{2}\) 个数和第 \(\frac{n + m}{2} + 1\) 个数的平均数。如果我们能实现一个函数，传入 \(k\)，返回 \(c\) 中第 \(k\) 个数，那么原问题自然也就迎刃而解了。

至此，我们把原问题转化为：

给出数列 \(a, b\) 和数字 \(k\)，要求在 \(\mathcal{O}(\log(n + m))\) 时间里求出 \(c\) 中第 \(k\) 个数。

于是我们成功避免了关于中位数的繁杂分类讨论。接下来考虑转化后的问题。

二、一些不成熟的想法（想看正解可以跳过本节）

第一想法是先把两个数组归并排序，但是这样做时间复杂度至少为 \(\mathcal{O}(n + m)\)。

另一想法是二分：不妨假设答案在 \(a\) 中，那么我们在 \(a\) 里二分答案。在 \(\text{check}\) 时，我们要求出当前的 \(a_{\text{mid}}\) 在 \(c\) 里排第几，也就是说 \(a\) 和 \(b\) 中一共有多少个比 \(a_{\text{mid}}\) 小的数。\(a\) 里显然有 \(\text{mid} - 1\) 个，而求 \(b\) 里有多少个，则需要在 \(b\) 里再次二分（或者用 \(\texttt{C++}\) 自带的 lower_bound，时间复杂度是一样的）。于是，两次二分套起来，总时间复杂度是 \(\mathcal{O}(\log^2(n + m))\)，仍不能令人满意。

三、真正解法

\(c\) 里的数要么来自 \(a\)，要么来自 \(b\)。考虑 \(c\) 的前 \(k\) 个数中，有多少个数来自 \(a\)，记为 \(x\)。则有 \(k - x\) 个数来自 \(b\)。那么，必定有：\(\max(a_x, b_{k - x}) \leq \min(a_{x + 1}, b_{k - x + 1})\)，因为 \(c\) 前 \(k\) 个数中任意一个，一定小于等于后 \(n + m - k\) 中任意一个（注：此处默认在 \(a, b\) 的最前面、最后面分别塞一个 \(-\infty, +\infty\)，这样可以避免类似 \(x = 0\) 或 \(x = n\) 的这种尴尬的边界情况）。

另外，如果知道了 \(x\)，显然也就知道了我们要求的 \(c\) 中第 \(k\) 个数（它就是 \(\max(a_x, b_{k - x})\)）。

怎么求 \(x\) 呢？我们先随便猜一个值 \(x'\)。那么：

• 若 \(x' = x\)，根据刚才的讨论，有：\(\max(a_x, b_{k - x}) \leq \min(a_{x + 1}, b_{k - x + 1})\)。
• 若 \(x' < x\)，相当于前 \(k\) 个数里来自 \(a\) 的太少了，来自 \(b\) 的太多了，所以 \(a_{x'}\) 太小，而 \(b_{k - x'}\) 太大。应该从后 \(n + m - k\) 个数里把一些来自 \(a\) 的数拿到前面来，替换掉前 \(k\) 个数里来自 \(b\) 的数。因此，此时有：\(b_{k - x'} > a_{x' + 1}\)。
• 若 \(x' > x\)，与上一条同理：前 \(k\) 个数里来自 \(a\) 的太多了，来自 \(b\) 的太少了，所以 \(a_{x'}\) 太大，而 \(b_{k - x'}\) 太小。应该从后 \(n + m - k\) 个数里把一些来自 \(b\) 的数拿到前面来，替换掉前 \(k\) 个数里来自 \(a\) 的数。因此，此时有：\(a_{x'} > b_{k - x' + 1}\)。

想明白这些以后，我们发现，只要我们随便猜一个 \(x'\)，就能 \(\mathcal{O}(1)\) 判断出它是大了还是小了。于是可以二分 \(x'\)。至此，我们在 \(\mathcal{O}(\log(n + m))\) 的时间复杂度内解决了本题。

一个需要注意的细节是，可能的 \(x\) 的范围是 \([0, k] \cap [k - m, n] = [\max(0, k - m), \min(k, n)]\)。二分开始前这样设置好范围，就可以避免下标越界的问题。

参考代码：

class Solution {
public:
	const int INF = 1e6 + 5;
	int n, m;
	double find(vector<int>& a, vector<int>& b, int K) {
		int l = max(0, K - m), r = min(n, K);
		// 前 K 个里有多少个来自 a
		while (l <= r) {
			int from_a = (l + r) >> 1; // mid
			int from_b = K - from_a;
			
			assert(from_b >= 0);
			assert(from_b <= m);
			
			int la, lb, ra, rb;
			if (from_a == 0) la = -INF;
			else la = a[from_a - 1];
			if (from_b == 0) lb = -INF;
			else lb = b[from_b - 1];
			if (from_a == n) ra = INF;
			else ra = a[from_a];
			if (from_b == m) rb = INF;
			else rb = b[from_b];
			
			if (max(la, lb) <= min(ra, rb)) {
				return max(la, lb);
			} else {
				if (la > rb) {
					r = from_a - 1;
				} else {
					assert(lb > ra);
					l = from_a + 1;
				}
			}
		}
		assert(0);
	}
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		n = nums1.size();
		m = nums2.size();
		
		if ((n + m) & 1) {
			return find(nums1, nums2, (n + m) / 2 + 1);
		} else {
			double x = find(nums1, nums2, (n + m) / 2);
			double y = find(nums1, nums2, (n + m) / 2 + 1);
			return (x + y) / 2.0;
		}
	}
};

这篇关于LeetCode 小水题选做的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！