[Java] LeetCode 4번 Median of Two Sorted Arrays

문제의 조건에서는 O(log(m+n))으로 풀라고 주어졌다. 차근차근 접근하기위해서 느린방법으로 먼저 풀어보았다.

1. O(m+n) 시간복잡도 풀이

중간값을 찾기 위해서 두개의 배열을 합쳐준다. 병합정렬(merge sort)에서 두개의 배열을 합쳐주는 작업과 흡사하다. 두개의 배열의 값들을 비교해서 작은 값을 추가하고 인덱스를 증가시킨다. 인덱스가 전부 증가된 이후에는 남은 배열들을 추가해주는 작업을 해주면 된다.

합친 후에는 홀수개인지 짝수개인지에 따라서 값을 계산해주었다.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int[] nums = new int[n1 + n2];

        int c1 = 0;
        int c2 = 0;
        double ans = 0.0;
        for (int i = 0; i < n1 + n2; i++) {
            if (c1 < n1 && c2 < n2) {
                if (nums1[c1] <= nums2[c2]) {
                    nums[i] = nums1[c1++];

                } else {
                    nums[i] = nums2[c2++];
                }
            } else if (c1 < n1) {
                nums[i] = nums1[c1++];
            } else {
                nums[i] = nums2[c2++];
            }
        }
        if ((n1 + n2) % 2 == 0) {
            int mid = (n1 + n2) / 2;
            ans = ((double) nums[mid - 1] + nums[mid]) / 2;
        } else {
            ans = nums[(n1 + n2) / 2];
        }
        return ans;
    }
}

2. O(log(m + n )) 풀이

나 혼자 힘을 풀 수 없어서 인터넷이 있는 풀이를 참고하였다. 

nums1[0], nums1[1], ... , nums1[i - 1] | nums1[i], ... , nums1[m - 1]

nums2[0], nums2[1], ... , nums2[j - 1] | nums2[j], ... , nums2[n - 1]

nums1과 nums2를 같은 크기의  2개의 그룹으로 분리한다. 파란색 부분의 개수 == 빨간색 부분의 개수(짝수) 혹은 파란색 부분의 개수 == 빨간색 부분의 개수 + 1 (홀수)을 만족하도록 한다. 그리고 왼쪽에 있는 파란색부분이 오른쪽에 있는 빨간색 부분보다 작거나 같아야한다. 즉 nums1[i - 1] <= nums2[j] 와 nums2[j - 1] <= nums1[i]를 만족해야된다. 

이분 탐색을 이용해서 해당 조건을 만족하는 i 와 j 값을 찾아준다. 

1) 짝수개의 경우를 보자

i + j = m - i + n - j 이고, j = (m + n) /2 - i 가 된다.

이때 max(nums1[i-1], nums2[j-1]) 이 중간값 왼쪽 부분이 된다. 그리고 중간값 오른쪽 부분은 min(nums1[i], nums2[j]) 가 된다. 이 둘을 더해서 평균을 내면 정답이 된다.

2) 홀수개의 경우를 보자.

나는 파란색 부분이 1개 더 많게 구분할 것이다. 

i + j = m - i + n - j + 1 이고, j = (m + n + 1) /2 - i 이 된다. 

이 때 파란색 부분이 1개 더 많으므로 max(nums1[i-1], nums2[j-1]) 이 중간값이 된다. 

i와 j 값이 각각 0과 m, n값일 때에는 따로 처리를 해주었다.

그리고 j를 구할 때도, 짝수인 경우에도 정수의 나숫셈 특징을 적용하여 (m + n + 1)/2 - i 수식을 적용하여도 된다. 그래서 j를 구하는 수식은 동일하게 적용되었다.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double ans;
        if (nums1.length > nums2.length) {
            int[] numsTemp;
            numsTemp = nums1;
            nums1 = nums2;
            nums2 = numsTemp;
        }
        int m = nums1.length;
        int n = nums2.length;
        int l = 0;
        int r = m - 1;
        int leftMax = -1;
        int rightMax = -1;
        int i = 0;
        int j = 0;
        while (l <= r) {
            i = l + (r - l) / 2;
            j = (n + m + 1) / 2 - i;
            if (i > 0 && nums1[i - 1] > nums2[j]) {
                r = i - 1;
            } else if (j > 0 && nums2[j - 1] > nums1[i]) {
                l = i + 1;
            } else {
                break;
            }
        }
        i = l + (r - l) / 2;
        j = (n + m + 1) / 2 - i;

        // 왼쪽 최대값
        if (i == 0) {
            leftMax = nums2[j - 1];
        } else if (j == 0) {
            leftMax = nums1[i - 1];
        } else {
            leftMax = Math.max(nums1[i - 1], nums2[j - 1]);
        }

        // 오른쪽 최소값
        if (i < m && j < n) {
            rightMax = Math.min(nums1[i], nums2[j]);
        } else if (i < m) {
            rightMax = nums1[i];
        } else if (j < n) {
            rightMax = nums2[j];
        }

        if ((m + n) % 2 == 0) {
            ans = (leftMax + rightMax) / 2.0;
        } else {
            ans = leftMax;
        }
        return ans;
    }
}