LeetCode in C# 4. Median of Two Sorted Arrays

문제 요약

두 배열의 중간 값을 반환해라. 단, 시간 복잡도는 O(log(m+n))안으로 해결해야한다.

 

문제 핵심 (주관적)

1. 두 배열을 더한 뒤에, 중간 값을 찾으면 간단하지만 그럴경우 시간 복잡도 조건을 충족 시킬 수 없다.

2. 두 배열을 더하지 않고 중간 값을 찾을 수 있는 방법을 모색해야한다.  

 

풀이방법

배열 두개를 합치지 않고, 중간 값을 찾을 수 있는 방법이 떠오르지 않아, 여러가지 참고 자료를 보면서 해결법을 찾았습니다. 바이너리 탐색을 활용해야하며, 핵심은 아래와 같습니다.  

 

풀이 핵심

두 배열을 합쳤을 때, 절반이 어떻게 나뉠지를 생각하면서 배열을 각각 좌측 부분과 우측부분으로 나눠야합니다.

좌측과 우측이 합쳐졌을 때를 기준으로 잘 나뉘어졌는지 판단할 수 있어야하는데, 

각 배열의 좌측의 마지막이 우측의 첫번째를 비교했을 때, 작거나 같음을 통해 판단할 수 있습니다.  

 

아래 링크를 통해 자세한 문제 해결 과정을 알 수 있습니다.

https://youtu.be/q6IEA26hvXc?si=xJ6eEXvJ8zPdSMn7

 

시간복잡도 : O(log(m+n))

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        // nums1이 무조건 더 짧도록 보장
        if (nums1.Length > nums2.Length) {
            var temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.Length;
        int n = nums2.Length;
        int left = 0, right = m;

        while (left <= right) {
            int i = (left + right) / 2; // num1의 중간 포인터
            int j = (m + n + 1) / 2 - i; // num2의 중간 포인터

            // 인덱스가 범위 예외처리
            int maxLeftA = (i == 0) ? int.MinValue : nums1[i - 1];
            int minRightA = (i == m) ? int.MaxValue : nums1[i];

            int maxLeftB = (j == 0) ? int.MinValue : nums2[j - 1];
            int minRightB = (j == n) ? int.MaxValue : nums2[j];

            // 좌측과 우측이 잘 나뉘어졌다면
            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
                //짝수인 경우
                if ((m + n) % 2 == 0) 
                    return (Math.Max(maxLeftA, maxLeftB) + Math.Min(minRightA, minRightB)) / 2f;

                //홀수인 경우
                else return Math.Max(maxLeftA, maxLeftB);
            } 
            
            //잘못나뉜 경우 포인터 이동
            else if (maxLeftA > minRightB)  
                right = i - 1; 
            
            else left = i + 1;
        }

        return 0; //실행 될일 없음
    }
}