algorithm/javascript/code/sort/medianOfTwoSortedArrays.js at master · yangfcm/algorithm · GitHub

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * Given two sorted arrays nums1 and nums2 of size m and n,
 * return the median of the two sorted arrays.
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @returns {number}
 */
function medianOfTwoSortedArraysSolution1(nums1, nums2) {
  let m = nums1.length;
  let n = nums2.length;

  if (m > n) {
    [nums1, nums2, m, n] = [nums2, nums1, n, m];
  }
  let low = 0,
    high = m;
  const halfLen = Math.floor((m + n + 1) / 2);
  while (low <= high) {
    const i = Math.floor((low + high) / 2);
    const j = halfLen - i;

    const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
    const minRight1 = i === m ? Infinity : nums1[i];
    const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
    const minRight2 = j === n ? Infinity : nums2[j];

    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      if ((m + n) % 2 === 0) {
        return (
          (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2
        );
      } else {
        return Math.max(maxLeft1, maxLeft2);
      }
    } else if (maxLeft1 > minRight2) {
      high = i - 1;
    } else {
      low = i + 1;
    }
  }
  throw new Error("Input arrays are not sorted or valid.");
}

/**
 * Given two sorted arrays nums1 and nums2 of size m and n,
 * return the median of the two sorted arrays.
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @returns {number}
 */
function medianOfTwoSortedArraysSolution2(nums1, nums2) {
  const m = nums1.length;
  const n = nums2.length;
  const f = (i, j, k) => {
    if (i >= m) return nums2[j + k - 1];
    if (j >= n) return nums1[i + k - 1];
    if (k === 1) return Math.min(nums1[i], nums2[j]);

    const mid1 =
      i + Math.floor(k / 2) - 1 < m
        ? nums1[i + Math.floor(k / 2) - 1]
        : Infinity;
    const mid2 =
      j + Math.floor(k / 2) - 1 < n
        ? nums2[j + Math.floor(k / 2) - 1]
        : Infinity;

    if (mid1 < mid2) {
      return f(i + Math.floor(k / 2), j, k - Math.floor(k / 2));
    } else {
      return f(i, j + Math.floor(k / 2), k - Math.floor(k / 2));
    }
  };
  const a = f(0, 0, Math.floor((m + n + 1) / 2));
  const b = f(0, 0, Math.floor((m + n + 2) / 2));
  return (a + b) / 2;
}

module.exports = {
  medianOfTwoSortedArraysSolution1,
  medianOfTwoSortedArraysSolution2,
};