[LeetCode] Median Of Two Sorted Arrays

문제링크

Median of Two Sorted Arrays - LeetCode

 

오름차순으로 정렬된 num1, num2를 병합하여 median 값을 반환하는 문제이다.
median 값이란 병합한 배열의 중앙값을 의미하고 배열이 짝수일때는 2개, 배열이 홀수일때는 1개가 해당된다.
예) [1,2,3,4,5] 의 median은 3, [1,2,3,4,5,6]의 median은 (3 + 4) / 2

조건 : time complexity should be O(log (m+n))

접근 방법
두 배열을 병합하여 sort를 사용하고 mid Index를 구해서 해결하는 방법이 쉽긴 하지만 JS의 기본 sort 메서드는 nlog(n)의 시간복잡도를 갖는다.

때문에 다른 방식으로 접근하였다.

1. 병합한 전체 길이와 midIndex를 배열 형태로 구한다. (짝수일때와 홀수일때를 나눠서)

const totalLen = nums1.length + nums2.length;
const midIndex = totalLen % 2 === 0 ?  [totalLen / 2 - 1,  totalLen / 2] : [Math.floor(totalLen / 2)] ;​

2. 병합한 배열을 담는 mergeArr 배열을 생성하고 mergeArr의 길이가 midIndex[0] + 1일때까지 아래 로직을 반복한다.
(짝수를 기준으로 midIndex[0] + 1을 잡음)

const mergeArr = [];
let indexOne = 0;
let indexTwo = 0;

while(mergeArr.length <= midIndex[0] + 1){
    if(nums1[indexOne] > nums2[indexTwo] || nums1[indexOne] === undefined){
        mergeArr.push(nums2[indexTwo])
        indexTwo++;
    }else{
        mergeArr.push(nums1[indexOne])
        indexOne++;
    }
}

만약 nums1 또는 nums2가 끝까지 진행되어 index(One,Two)++이 실행되면 undefined가 출력되므로 해당 처리를 해줘야한다.

3. 만들어진 mergeArr를 midIndex의 길이가 2일때와 1일때를 구분짓고 해당 index를 반환하여 결과를 출력한다.

return midIndex.length === 2 ? (mergeArr[midIndex[0]] + mergeArr[midIndex[1]]) / 2 : mergeArr[midIndex[0]];

sort를 이용하면 3줄로 풀이가 가능하지만 위의 방법과 Runtime 시간의 차이가 발생한다.


시간복잡도를 고려한 풀이

sort를 사용한 풀이

 

// 시간복잡도를 고려한 풀이

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const mergeArr = [];
    let indexOne = 0;
    let indexTwo = 0;
    const totalLen = nums1.length + nums2.length;
    const midIndex = totalLen % 2 === 0 ?  [totalLen / 2 - 1,  totalLen / 2] : [Math.floor(totalLen / 2)] ;
    
    while(mergeArr.length <= midIndex[0] + 1){
        if(nums1[indexOne] > nums2[indexTwo] || nums1[indexOne] === undefined){
            mergeArr.push(nums2[indexTwo])
            indexTwo++;
        }else{
            mergeArr.push(nums1[indexOne])
            indexOne++;
        }
    }
    
    return midIndex.length === 2 ? (mergeArr[midIndex[0]] + mergeArr[midIndex[1]]) / 2 : mergeArr[midIndex[0]];
};

 

// sort를 사용한 풀이

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
 var findMedianSortedArrays = function(nums1, nums2) {
    const mergeArr = [...nums1,...nums2].sort((a,b) => a-b);
    const totalLen = mergeArr.length;
    const midIndex = totalLen % 2 === 0 ?  [totalLen / 2 - 1,  totalLen / 2] : [Math.floor(totalLen / 2)]
    
    return midIndex.length === 2 ? (mergeArr[midIndex[0]] + mergeArr[midIndex[1]]) / 2 : mergeArr[midIndex[0]];
};