<Hard> Median of Two Sorted Arrays (LeetCode : C#)

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

📕 문제 설명

두 정렬된 정수 배열이 주어졌을 때 이를 합친 배열에서 median 찾아서 반환하기

• Input
  두 정렬된 정수 배열 nums1, nums2
• Output
  두 배열을 합친 후 median

예제

풀이

난이도 보고 처음에는 복잡하게 생각하다가 그냥 제일 간단한 방식으로도 O(m+n)안에는 들어올 것 같아서 해봤더니 통과했다.

그냥 두 배열 합쳐서 정렬한 후 짝수 홀수 케이스 나눠서 메디안 구하는 방식이다. 시간 복잡도가 정렬할 때 O(m+n)이면 되어서 이 방식으로 진행했다.

문제를 잘못 읽은거였다 ㅎ.. O(log(m+n)) 안에 들어와야한다. 우선 잘못 보고 풀었을 때 정렬을 써서 0(nlog(n))이라 통과가 안될텐데 왜 통과되었을까 싶은 의문이.. 추후 다른 방식으로 풀어봐야겠다!

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int[] merged = nums1.Concat(nums2).ToArray();
        Array.Sort(merged);
        int count = merged.Length;
        double result = count % 2 == 0 ? (merged[count / 2 - 1] + merged[count / 2]) / 2f : merged[count / 2];

         return result;
        
    }
}

결과