[Algorithm] Median of Two Sorted Arrays

Question:

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.

 

주어진 두개의 배열을 병합하고 그 중간값을 구하는 문제 입니다.

 

Solution:

먼저 두개의 배열을 병합하고 정렬을 시켜줍니다. 정렬된 배열의 수가 홀수 이면 중간 값을 결과값에 넣어주고, 짝수이면 가운데 2 요소를 더하여 둘로 나눈 중간값을 구해줍니다.

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums3 = new int[nums1.Length + nums2.Length]; // 두 개의 배열을 병합할 배열
        double result = 0; // 결과로 반환될 중간값

        Array.Copy(nums1, nums3, nums1.Length); // 병합할 배열에 첫번째 배열 복사
        Array.Copy(nums2,0, nums3, nums1.Length, nums2.Length); // 병합할 배열에 두번째 배열 복사
        Array.Sort(nums3); // 병합한 배열 정렬

        foreach(var e in nums3)
        {
            Console.WriteLine(e);
        }

        int n = nums3.Length; // 요소 갯수 확인

        if(n % 2 == 1)
        {
            result = nums3[(n/2)]; // 홀수이면 중간값을 반환
        }else{
            result = (nums3[n/2-1] + nums3[n/2]) / 2.0; // 짝수이면 두개의 중간 요소를 구하여 중간값을 반환
        }

        return result;
    }
}

First, merge two arrays to result array and sort the result array. If the number of result array is odd, insert the median value into the result, and if it is even, add the middle two elements to find the median value divided by two.