[Leetcode] 4. Median of Two Sorted Arrays

정렬된 두 개의 정수 배열 num1, num2 가 있다. 이 두 배열을 합쳤을 때의 중앙값 을 구하는 문제. 평균이 아니라 중앙값(median) 이다.

두 배열이 이미 정렬된 상태이기 때문에 앞에서부터 두 배열의 원소들을 비교해나가면서 중앙값 까지만 계산하면 된다. 따라서 시간복잡도 O(log(nums1.length + nums2.length)) 에 끝낼 수 있다.

두 배열에서 각각 값을 꺼내어 비교하고 결과값을 정리할 배열 arr 에 작은값을 집어넣는다. 두 배열의 길이가 같다는 보장이 없으므로 한쪽 배열이 먼저 끝난 경우엔 중앙에 도달할 때 까지 다른 배열을 arr 에 넣는다. arr.length 가 median 이상이라면 연산을 중단하고 값을 꺼내면 된다. num1.length + nums2.length가 짝수인 경우 가운데 있는 두 값을 꺼내 평균을 내서 반환해야 한다.

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    const m = nums1.length;
    const n = nums2.length;

    const medianIndex = Math.floor((m + n) / 2);
    let medianValue = 0;

    let arr = [];
    let i1 = 0;
    let i2 = 0;

    while (arr.length <= medianIndex) {
        const val1 = nums1[i1];
        const val2 = nums2[i2];

        if (i1 === m) {
            arr.push(val2);
            i2 += 1;
            continue;
        }

        if (i2 === n) {
            arr.push(val1);
            i1 += 1;
            continue;
        }

        if (val1 === val2) {
            arr.push(val1);
            arr.push(val2);
            i1 += 1;
            i2 += 1;
        } else if (val1 > val2) {
            arr.push(val2);
            i2 += 1;
        } else {
            arr.push(val1);
            i1 += 1;
        }
    }

    let answer = arr[medianIndex]

    if (((m + n) % 2) === 0) {
        answer = (arr[medianIndex] + arr[medianIndex - 1]) / 2
    }

    return answer;
};