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

发表于 分类于 阅读次数：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

1
2
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

实现方式一:

时间复杂度：遍历全部数组 O(m+n)；空间复杂度：开辟了一个数组，保存合并后的两个数组 O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  var arr = nums1.concat(nums2);
  arr.sort((a, b) => a - b);
  if (arr.length % 2 === 0) {
    return (arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2;
  } else {
    return arr[(arr.length - 1) / 2];
  }
};

解法二：

时间复杂度依旧是 O(m+n)；空间复杂度 O(1)

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
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  var m = nums1.length;
  var n = nums2.length;
  var len = m + n,
    left = 0,
    right = 0,
    aStart = 0,
    bStart = 0;
  for (let i = 0; i <= len / 2; i++) {
    left = right;
    if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
      right = nums1[aStart++];
    } else {
      right = nums2[bStart++];
    }
  }
  if (len % 2 === 0) {
    return (left + right) / 2;
  } else {
    return right;
  }
};

解法三：

时间复杂度依旧是 O(log(m+n))，空间复杂度 O(1)。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  var n = nums1.length;
  var m = nums2.length;
  var left = Math.floor((n + m + 1) / 2);
  var right = Math.floor((n + m + 2) / 2);
  return (
    (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) +
      getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) *
    0.5
  );
};

function getKth(nums1, start1, end1, nums2, start2, end2, k) {
  var len1 = end1 - start1 + 1;
  var len2 = end2 - start2 + 1;
  if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);

  if (len1 == 0) return nums2[start2 + k - 1];

  if (k == 1) return Math.min(nums1[start1], nums2[start2]);

  var i = start1 + Math.min(len1, Math.floor(k / 2)) - 1;
  var j = start2 + Math.min(len2, Math.floor(k / 2)) - 1;

  if (nums1[i] > nums2[j]) {
    return getKth(
      nums1,
      start1,
      end1,
      nums2,
      j + 1,
      end2,
      k - (j - start2 + 1)
    );
  } else {
    return getKth(
      nums1,
      i + 1,
      end1,
      nums2,
      start2,
      end2,
      k - (i - start1 + 1)
    );
  }
}