[LeetCode] - 4. Median of Two Sorted Arrays

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '어려움 (Hard)' 단계인 "Median of Two Sorted Arrays" 문제입니다.

--> https://leetcode.com/problems/median-of-two-sorted-arrays/description/

 

문제 : 

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

---

Example 1 :

Input : nums1 = [1,3], nums2 = [2]

Output : 2.00000

Explanation : merged array = [1,2,3] and median is 2.

 

Example 2 :

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.

 

Constraints :

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

---

이 문제는 두 개의 정렬된 배열 nums1과 nums2가 주어졌을 때, 두 배열을 병합하여 정렬된 상태로 만들고 중앙값(median)을 반환하는 문제입니다. 이 문제는 O(log(m+n)) 시간 복잡도로 해결해야 합니다. 예를 들어, 입력이 [1,3]과 [2]인 경우 병합된 배열은 [1,2,3]이며 중앙값은 2입니다.

 

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[] merged = new int[n + m];

        double median = 0.0;

        for (int i = 0; i < n; i++) {
        merged[i] = nums1[i];
        }

        for (int i = 0; i < m; i++) {
            merged[i + n] = nums2[i];
        }
        Arrays.sort(merged);

        // Calculating the median
        if ((n + m) % 2 != 0) { // Odd length
            return merged[(n + m) / 2];
        } else { // Even length
            return (merged[(n + m) / 2 - 1] + merged[(n + m) / 2]) / 2.0;
        }

    }
}

 

제 코드를 단계별로 나뉘어서 설명을 드리자면 : 

1. 배열 병합:
   • nums1의 요소들을 merged 배열의 앞부분에 복사합니다.
   • nums2의 요소들을 merged 배열의 뒷부분에 복사합니다.
2. 병합된 배열 정렬:
   • 병합된 배열을 정렬합니다.
3. 중앙값 계산:
   • 병합된 배열의 길이가 홀수인 경우 중앙값은 중간 요소입니다.
   • 병합된 배열의 길이가 짝수인 경우 중앙값은 중앙의 두 요소의 평균입니다.

시간 복잡도:

1. 병합:
   • 두 배열을 병합하는 데 걸리는 시간은 O(n + m)입니다.
2. 정렬:
   • 병합된 배열을 정렬하는 데 걸리는 시간은 O((n + m) log(n + m))입니다.
3. 중앙값 계산:
   • 중앙값을 계산하는 데 걸리는 시간은 O(1)입니다.

따라서 전체 시간 복잡도는 O((n + m) log(n + m))입니다.

공간 복잡도:

• 병합된 배열을 저장하기 위해 O(n + m)의 추가 공간이 필요합니다.
• 따라서 공간 복잡도는 O(n + m)입니다.

 

하지만 ! 제 방법은 시간 복잡도와 공간 복잡도 측면에서 비효율적입니다. 문제에서 요구하는 O(log(m+n)) 시간 복잡도를 만족하지 않습니다. 이 문제를 해결하는 더 효율적인 방법은 결국은 이진 탐색을 사용하는 것입니다.

---

개선된 코드 : 

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.length;
        int n = nums2.length;
        int halfLen = (m + n + 1) / 2;
        int imin = 0, imax = m;

        while (imin <= imax) {
            int i = (imin + imax) / 2;
            int j = halfLen - i;

            if (i < m && nums1[i] < nums2[j - 1]) {
                imin = i + 1;
            } else if (i > 0 && nums1[i - 1] > nums2[j]) {
                imax = i - 1;
            } else {
                int maxOfLeft;
                if (i == 0) {
                    maxOfLeft = nums2[j - 1];
                } else if (j == 0) {
                    maxOfLeft = nums1[i - 1];
                } else {
                    maxOfLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return maxOfLeft;
                }

                int minOfRight;
                if (i == m) {
                    minOfRight = nums2[j];
                } else if (j == n) {
                    minOfRight = nums1[i];
                } else {
                    minOfRight = Math.min(nums1[i], nums2[j]);
                }

                return (maxOfLeft + minOfRight) / 2.0;
            }
        }
        return 0.0;
    }
}

 

이 코드는 이진 탐색을 사용하여 두 배열의 중앙값을 효율적으로 찾고 문제가 요구하는 O(log(m+n)) 의 시간 복잡도를 지니고 있습니다.

---

이진 탐색 하기 전 후의 Runtime 결과