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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int tot = nums1.size() + nums2.size();
    if (tot % 2 == 0) {
      int left = find(nums1, 0, nums2, 0, tot / 2);
      int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
      return (left + right) / 2.0;
    } else {
      return find(nums1, 0, nums2, 0, tot / 2 + 1);
    }
  }
  // 在 nums1 [i...] 和 nums2[j...] 组成的大数组里找排名第 k 的数
  int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
    // 总是假定 nums2 数组短
    if (nums1.size() - i > nums2.size() - j) {
      return find(nums2, j, nums1, i, k);
    }
    if (k == 1) {
      if (nums1.size() == i) {
        return nums2[j];
      } else {
        return min(nums1[i], nums2[j]);
      }
    }
    if (nums1.size() == i) {
      return nums2[j + k - 1];
    }
    int si = min(i + k / 2, (int)nums1.size()), sj = j + k - k / 2;
    if (nums1[si - 1] > nums2[sj - 1]) {
      return find(nums1, i, nums2, sj, k - (sj - j));
    } else {
      return find(nums1, si, nums2, j, k - (si - i));
    }
  }
};