原题：寻找两个正序数组的中位数

思路：计算出中位数需要遍历数组的次数，接着按从小到大的顺序遍历两数组直到步数 = 次数

思路

  1. 计算需要走多少步记为 end；判断两数组总长度是否为偶数 flag；初始化两个变量记录当前值和上一个值（偶数时需要计算两数平均值）left = 0, right = 0

  2. 使用两个指针 let i = -1, j = -1 开始遍历两数组；使用计数 let step = 0 记录步数

  3. 如果第一个数组走到尽头，或者第一个数组的下一个值大于第二个数组的下一个值时 nums[i + 1] === undefined || nums1[i + 1] > nums2[j + 1]，移动第二个数组的指针，步数增加，更新当前数和上一个数

  4. 或者第二个数组走到尽头，或者第二个数组的下一个值大于等于第一个数组的下一个值时 nums2[j + 1] === undefined || nums2[j + 1] >= nums1[i + 1]，移动第一个数组的指针，步数增加，更新当前数和上一个数

  5. 如果走够了步数，根据前记录的奇偶返回对应的中间值

1. 计算需要几步

这里举个例子

假设两数组总长度为偶数 6，那么 6 / 2 = 3，偶数需要中间的两个数，所以我们遍历到中间的第二个数即 6 / 2 + 1 = 4 步

假设两数组总长度为奇数 5，那么 5 / 2 = 2.5，奇数只需要中间的一个数，所以我们遍历到 floor(5 / 2) + 1 = 3 或者 ceil(5 / 2) = 3 即可

为了奇偶数计算一致，我们选择向下取整 + 1 的算法

1
2
3
const len = nums1.length + nums2.length;
// 可以走多少步
const end = Math.floor(len / 2) + 1;

2. 初始化需要的变量

1
2
3
4
5
// 是否为偶数
const flag = len % 2 === 0;
// 初始化当前数和上一个数为 0
let left = 0;
let right = 0;

3. 遍历两个数组

用两个指针指向两个数组，同时用一个遍历记录步数

因为我们指向第一个元素时也需要计步，所以这里指针初始化为 -1

1
2
3
for (let i = -1, j = -1, step = 0; ; ) {
  ...
}

接着就是实现上面的思路，保证从小到大遍历两个数组，每次只走其中一侧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 如果 nums1 走到头 || nums1 下一个数大于 nums2 下一个数
if (nums1[i + 1] === undefined || nums1[i + 1] > nums2[j + 1]) {
  // 移动 nums2
  j++;
  // 计数
  step++;
  // 更新上一个数
  left = right;
  // 更新当前数
  right = nums2[j];
  // 如果 nums2 走到头 || nums2 下一个数大于 nums1 下一个数
} else if (nums2[j + 1] === undefined || nums2[j + 1] >= nums1[i + 1]) {
  // 移动 nums1
  i++;
  // 计数
  step++;
  // 更新上一个数
  left = right;
  // 更新当前数
  right = nums1[i];
}

走够步数后

1
2
3
4
5
// 如果已经走够了步数
if (step === end) {
  // 如果是偶数，返回当前数和上一个数的平均值，否则返回当前数
  return flag ? (right + left) / 2 : right;
}

完整代码

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
52
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  const len = nums1.length + nums2.length;
  /**
   * 【重点】
   * 如果我们 len 为偶数 6，那么 6 / 2 = 3
   * 我们需要中间的两个数，所以步数为 6 / 2 + 1 = 4
   * 如果我们是 len 为奇数 5，那么 5 / 2 = 2.5
   * 我们需要中间的一个数，需要走 3 步，可以为 floor(5 / 2) + 1 或者 ceil(5 / 2)
   * 为了奇偶能用同一套计算方法，我们写作 Math.floor(len / 2) + 1
   */
  // 可以走多少步
  const end = Math.floor(len / 2) + 1;
  // 是否为偶数
  const flag = len % 2 === 0;
  // 初始化当前数和上一个数为 0
  let left = 0;
  let right = 0;
  // 因为需要对每个下标计数，所以从 -1 开始，每次对比下一个数
  for (let i = -1, j = -1, step = 0; ; ) {
    // 如果 nums1 走到头 || nums1 下一个数大于 nums2 下一个数
    if (nums1[i + 1] === undefined || nums1[i + 1] > nums2[j + 1]) {
      // 移动 nums2
      j++;
      // 计数
      step++;
      // 更新上一个数
      left = right;
      // 更新当前数
      right = nums2[j];
      // 如果 nums2 走到头 || nums2 下一个数大于 nums1 下一个数
    } else if (nums2[j + 1] === undefined || nums2[j + 1] >= nums1[i + 1]) {
      // 移动 nums1
      i++;
      // 计数
      step++;
      // 更新上一个数
      left = right;
      // 更新当前数
      right = nums1[i];
    }
    // 如果已经走够了步数
    if (step === end) {
      // 如果是偶数，返回当前数和上一个数的平均值，否则返回当前数
      return flag ? (right + left) / 2 : right;
    }
  }
};