LEETCODEHard

Median of Two Sorted Arrays

풀이일 2025 · 08 · 13기록 2 ms · 59.1 MB원문 leetcode ↗

ArrayBinary SearchDivide and Conquer

문제

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10⁶ <= nums1[i], nums2[i] <= 10⁶

풀이 TypeScript

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {

  const m = nums1.length;
  const n = nums2.length;

  if (m > n) return findMedianSortedArrays(nums2, nums1);

  const { MIN_SAFE_INTEGER, MAX_SAFE_INTEGER} = Number
  const { max, min, floor } = Math;

  const totalHalf = floor((m + n + 1) / 2);

  let left = 0;
  let right = m;

  while (left <= right) {
    const i = floor((left + right) / 2);
    const j = totalHalf - i;

    const nums1Left = (i > 0) ? nums1[i - 1] : MIN_SAFE_INTEGER;
    const nums1Right = (i < m) ? nums1[i] : MAX_SAFE_INTEGER;
    const nums2Left = (j > 0) ? nums2[j - 1] : MIN_SAFE_INTEGER;
    const nums2Right = (j < n) ? nums2[j] : MAX_SAFE_INTEGER;

    if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
      const maxLeft = max(nums1Left, nums2Left)
      const minRight = min(nums1Right, nums2Right)
      return (m + n) % 2 === 1 ? maxLeft : (maxLeft + minRight) / 2;
    }
    else if (nums1Left > nums2Right) {
      right = i - 1;
    }
    else {
      left = i + 1;
    }
  }
  return 0;
}

복사됨