在两个有序数组中找整体第k小的数

一、题目

给定两个已经排序的数组（假设按照升序排列），然后找出第K小的数。比如数组A = {1， 8， 10， 20}， B = {5， 9， 22， 110}， 第 3 小的数是 8.。要求时间复杂度O(logN)，空间复杂度O(1)。

二、解法

2.1、双指针

• 用两个指针pa、pb分别指向arr1、arr2。
  • 在初始状态，两个指针分别指向第一个起始值，即pa = 0， pb = 0。
  • 然后，我们开始进行比较，如果A数组的值比B数组的值小， 把A数组的指针pa向前移动，然后再进行比较。
  • 每次移动，我们都能够得到当前第 i 小的值（随着pa,pb 的移动，i 会逐渐变大）。
• 比如对于数组A = {1， 8， 10， 20}， B = {5， 9， 22， 110}
  • 初始时，pa = 0; pb = 0，因为(A[pa] = 1) < (B[pb] = 5), 所以，第 1 小的值为 1
  • 这个时候，我们会把 pa 向右移动，即 pa = 1, 并且 pb 保持不变: pb = 0.
  • 然后再次比较A[pa] 和 B[pb] 的值，因为 (A[pa] = 8) > (B[pb] = 5), 所以，第 2 小的值是 5, 然后，我们增加 pb 的值。
  • 请注意，如果我们用一个变量来保存当前第 i 小的值 (随着pa, pb的移动，i 的值也会增加，那个变量保存的值也会改变)。那么，当pa + pb = k 的时候，那么那个变量保存的一定是第 k 小的值。
• 这里要注意的是，当一个数组的指针已经“到头”了，这个时候怎么进行越界处理呢？我们这里可以用一个简单的判断语句就可以处理了。

2.2、二分查找

Pa+Pb+1=k；

Pa+Pb=k-1；

A[Pa-1]<B[Pb]&&B[Pb]<A[Pa];

B[Pb-1]<A[Pa]&&A[Pa]<B[Pb];

• 通过上面这段代码，我们实际上是把数组延长了，每个数组多了两个值Integer.MIN_VALUE,Integer.MAX_VALUE

  • 这样，当pa = 0 是，我们也可以得到A[pa - 1] 的值：Ai_1 = ((pa == 0) ? Integer.MIN_VALUE : A[pa-1]);
  • 当 pa =A.length 时，我们可以得到 A[pa]的值：Ai =(pa == A.length) ? Integer.MAX_VALUE : A[pa]。

• 这样，我们就不用担心越界的问题了。

有了上面的分析，代码就容易写出来了。

• 在程序里，我们设置 pa 的初始值为Math.min(A.length, k - 1)
• 然后，通过增加或者减少pa 的值，来使得 B[pb] < A[pa] && B[pb] > A[pa - 1] 或者A[pa] < B[pb] && A[pa] > B[pb - 1] 成立
• 代码中, delta 指的是 pa 的变化量，每次递归以后，delta的值变成一半。