카테고리 없음

leetcode0004 - Median of Two Sorted Arrays / Hard / TypeScript

eumjo_o 2023. 3. 31. 20:56

https://leetcode.com/problems/median-of-two-sorted-arrays/

 

Median of Two Sorted Arrays - LeetCode

Can you solve this real interview question? Median of Two Sorted Arrays - 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

leetcode.com

 

Time Complexity O(n+m), Space Complexity O(n+m)

  • nums1과 nums2 배열을 순차적으로 돌면서, 크기순으로 sorting
  • 배열의 크기 역시 O(n+m)

 

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    const sortedNums = Array(nums1.length + nums2.length);

    let index1 = 0;
    let index2 = 0;

    while(index1 < nums1.length || index2 < nums2.length) {
        if(index2 === nums2.length || nums1[index1] <= nums2[index2]) {
            sortedNums[index1 + index2] = nums1[index1];
            index1++;

            continue;
        } 

        if(index1 === nums1.length || nums2[index2] <= nums1[index1]) {
            sortedNums[index1 + index2] = nums2[index2];
            index2++;

            continue;
        }
    }

    const mediumNum = Math.floor(sortedNums.length / 2);

    if(sortedNums.length % 2 == 1) {
        return sortedNums[mediumNum];
    } else {
        return (sortedNums[mediumNum-1] + sortedNums[mediumNum]) / 2.0;
    }
};