找出长度为m和n的两个有序数组中的第k个数

算法 leetcode

初始假设

假设数组1的集合为M，每个数标记为$M_0, M_1,...M_{m-1}$；
数组2的集合为N，每个数标记为$N_0, N_1,...N_{n-1}$。
设数组1，2的合并后的有序集合为P，每个数标记为$P_0, P_1,...P_{m+n-1}$；此问既是要寻找$P_{k-1}$。

迭代过程

将$M_{x-1}$与$N_{y-1}$进行比较。

若$M_{x-1}>N_{y-1}$，则可知有$M_{x-1}>\{M_0,M_1,...M_{x-2},N_0,N_1,...N_{y-1}\}$。此时:
1. 若有$k < y$，则$P_{k-1} \in \{M_0,M_1,...M_{x-2},N_0,N_1,...N_{y-2}\}$，且是新的集合中的第k个数；
2. 若$y \leq k < x+y$，则有$P_{k-1} \in \{M_0,M_1,...M_{x-2},N_0,N_1,...N_{n-1}\}$，且是新的集合中的第k个数；
3. 若$x+y \leq k$，则有$P_{k-1} \in \{M_0,M_1,...M_{m-1},N_{y},...N_{n-1}\}$，且是新的集合中的第k-(y)个数；

若$M_{x-1}=N_{y-1}$，则$M_{x-1}$和$N_{y-1}$为有序集合P中的$P_{x+y-2}$和$P_{x+y-1}$此时：
1. 若有$k \leq x+y-2$，则$P_{k-1} \in \{M_0,M_1,...M_{x-2},N_0,N_1,...N_{y-2}\}$，且是新的集合中的第k个数；
2. 若有$x+y < k$，则$P_{k-1} \in \{M_x,M_{x+1},...M_{m-1},N_y,N_{y+1},...N_{n-1}\}$，且是新的集合中的第k个数；
3. 显然$k = x+y-1$或$k = x+y$时，有$P_{k-1}=M_{x-1} =N_{y-1}$。

通过前述的过程不断迭代，最后有$P_{k-1}$仅属于某一个数组集合，或$k=1$时，容易获得最终结果。