Leetcode - 4. Median of Two Sorted Arrays

문제

두개의 배열이 주어진다. 전체 배열값중 중간 위치의 값을 리턴하라. (배열이 홀수개면 중간 인덱스값, 짝수개면 두개의 평균값). 단 풀이의 시간복잡도는 O(log(m+n)) 이 되어야한다.

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.

해결 O(m+n)

말그대로 두 배열을 정렬된 순서로 합치고 중간값을 계산한 방법. 두 배열을 합치는 two pointer방법은 앞으로 많이 쓸 구조이므로 외워둘것.

O(log(m+n)) 방법이 떠오르지 않아서 일단 O(m+n)으로 푼건데, 답이 맞았음; 그것도 92%로.
Runtime: 14 ms, faster than 92.28%

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int retsize = nums1Size + nums2Size;
    int *ret = (int *)malloc(retsize * sizeof(int));
    int retcnt = 0;
    int i1 = 0, i2 = 0;
    
    while (retcnt < retsize) {
        if (i1 == nums1Size) {
            ret[retcnt++] = nums2[i2++];
            continue;
        }
        if (i2 == nums2Size) {
            ret[retcnt++] = nums1[i1++];
            continue;
        }
        if (nums1[i1] < nums2[i2]) {
            ret[retcnt++] = nums1[i1++];
        } else {
            ret[retcnt++] = nums2[i2++];
        }
    }
    
    int mid = retsize >> 1;
    if (retsize % 2 == 0)
        return (double)(ret[mid - 1] + ret[mid]) / 2;
    else 
        return ret[mid];
}