readme_draft

log(m+n)思路

题解 1

求两个有序数组的中位数，其中位数显然是由这两个数组中的一个或者两个关键元素决定的。同时，当确定该（一个或两个）关键元素后，位于这（一个或两个）关键元素左边的元素个数与后边的元素个数要趋近相等，这是其必要条件（但并非冲要条件），冲要条件需要再补一条，也就是两个数组内both左边的元素均小于（这一个或两个）关键元素，同时右边的要大于。

当两个数组的长度和为奇数的时候，该关键元素组必定只包含一个元素，且必定只在其中一个数组中决定；而当长度和为偶数时，该关键元素组必定包含两个元素，但可以由两个数组分别决定，也可以只由其中一个数组决定。为了统一这两种情况，我们可以直接使用两个指针表示目标关键组，当长度和为奇数时，两个指针指向同一个元素，否则分别指向两个元素。

接下来需要进一步明确这两个指针的终态状态。很显然，在终态时，两个数组内所有不比这两个指针小的元素的个数与不比这两个指针大的元素的个数可以相等（S0）（之所以要用这么复杂的表述，是因为需要考虑非严格递增数组的情况，比如N个5连在一起，且5恰好是这两个数组的中位数的时候，则N个元素中任取一个都可以是终态指针所指向位置）。但如此描述，并不适合编程，因此可进一步细化，即两个数组内所有在这两个指针左边的元素的个数与右边的相等（S1）。这个状态其实是前者的子集，但很适合编程实现。

但为了满足S1，我们需要在编程实现上做一次变通。考虑长度和为奇数导致关键元素必定只在某一个数组上的情况，假设该元素是$A_i$，按照S1，我们知道另一个元素也是$A_i$，但这会给编程造成困难，$A_i$和数组$B$之间是什么关系？我们就很不好说了，到底是$B>=A_i$还是$B<=A_i$呢？我们没法确定，为此，我们其实在编程时需要引入哨兵结点：在A、B两个数组的首尾分别添设一个哨兵结点$A_{-1}, A_{m}, B_{-1}, B_{n}$。这样比如说我们的终态是$(7, -1)$，这就表示A数组左边有7个（全部来自于A数组，下标从0到6），右边有m-8+n个（来自A数组的有m-1-7个，来自B数组的有n个）。

因此，我们推导出适合于编程实现的终态定义：位于AB两数组指针左右两侧的元素个数和相等，且满足 $A_{i}<=B_{j+1}, B_{j}<=A_{i+1}$（S2）。不过，值得注意的是，如果我们按照如此定义，也就是“向后看”以确定偏序关系的话，我们就不方便让指针指向末尾的哨兵了，否则我们需要添设三个哨兵，用以统一$A_n$和$B_m$。因为我们可以稍微改变一下我们指针的指示范围，让其限定在 $[-1, n-1], [-1, m-1]$ 内。我们可以验证一下边界情况：

1. 当终态为 $[k, -1]$，则需满足 $A_k <= B_0, B_{-1} <= A_k$，我们可以定义 $B_{-1} = -\infty$ 从而成立，这表示比 $A_k$ 小的有且只有位于 $A_k$ 左边的 k 个元素，而比 $A_k$ 大的包括位于 $A_k$ 后面的 $n-k-1$ 个元素与 B数组的全部元素
2. 当终态为 $[k, n-1]$，则需满足 $A_k <= B_n, B_{n-1} <= A_{k+1}$，我们可以定义 $B_n = \infty$ 从而成立，这表示比

但这只是一个文字表述，落实到数学上其实存在一定困难，主要要明确分界点是一个元素，还是元素之间的间隔。不妨先考虑两个数组的长度和为偶数，则中位数必然由其中两个元素决定，但这两个元素并非一定分别位于两个数组中，而是有可能只在一个数组里。所以如果我们强迫每个目标元素都需要要有指针指向的话，则为了指示另一个数组的状态，就必须要设计三个变量，这看起来有点丑陋。

南川题解Leetcode 4. Median of Two Sorted Arrays

要在两个有序数组 $A(n), B(m)$ 中找到合并后数组的中位数，即在这两个数组中分别找到两个分界点 $i, j$，使位于这两个分界点左边的元素个数总和（$i+j$）等于右边的元素个数总和（$n-i+m-j-2$），且所有位于左边的元素都不大于这两个分界点所指示的数值，所有位于右边的都不小于。

我们向两个数组的首尾分别增设一个哨兵结点 $A_{-1}, A_m, B_{-1}, B_n$，这样有当 $j=-1$ 时表示B数组所有元素都比 $A_i$ 大，而当 $j=n$ 时表示B数组所有元素都比 $A_i$ 小（$i$同理）。此时有：

• 奇数	偶数
  状态约束条件	$i + j = \lfloor(m+n)/2\rfloor$	$i + j = (m+n)/ 2 - 1$
  状态转移函数	$\left\{\begin{aligned}i右移j左移，&A_i <= B_{j+1} \cap B_j>A_{i+1} \\ i左移j右移，& A_i > B_{j+1} \cap B_j <= A_{i+1} \\ 不存在，& A_i > B_{j+1} \cap B_j > A_{i+1} \\ 终态，& A_i <= B_{j+1} \cap B_j <= A_{i+1}\\ \end{aligned}\right.$ 注：i和j每次左移右移的距离是相等的，方向是相反的，而步长是性能的关键：如果步长为1就退化为暴力枚举法，此处可以使用二分。在二分的过程中，但很重要的一点就是二分有概率会超过数组的界限，因此要做一个约束，例如如果是$i$往右滑动，可以设为 $\min \{k/2, m-i, j+1 \}$，反之则为 $\min \{k/2, i+1, n-j \}$。这里值得提及的是，一旦某个数组滑到了边界，由于我们约定 $i+j$ 始终满足数组长度和的一半，因此接下来一定会往另一个方向滑动，因而约束是有效且必要的。
  中位数计算	$ \left{\begin{aligned}\min {Ai, B_j}&, 0\le i \lt m, 0\le j\lt n \A{i-1} & , 0\le i \lt m, j=-1 \ Ai & , 0\le i \lt m, j=n \ B{j-1} & , i=-1, 0\le j \lt n \ B_j & , i = -1, 0\le j\lt n\end{aligned}\right.$	$ \left{\begin{aligned}(\max{Ai,B_j} + \min{A{i+1},B{j+1}})/2 &, 0\le i \lt m, 0\le j\lt n \ (A{i-1} + A{i})/2 & , 0\le i \lt m, j=-1 \ (A{i} + A{i+1})/2 & , 0\le i \lt m, j=n \ (B{j-1} + B{j})/2 & , i=-1, 0\le j \lt n \(B{j} + B_{j+1})/2 & , i = m, 0\le j\lt n\end{aligned}\right.$