[LeetCode] Median Two Sorted Arrays

문제

문제는 다음과 같다.
배열 2개가 주어지고 두 배열의 Median 값 (중간값을) 구하여라.

조건이 있다.
시간 복잡도는 $O(Log(m+n))$ 을 넘어선 안된다.

접근한 생각

두 배열을 합치고, 소팅작업만 잘해주면 되겠구나 라는 생각을 했다.
그런데 아무래도 일반 적인 배열을 제외하고 Quick이나 Merge를 사용해야 되겠다 생각했다.
O(Log(m+n))이니까,(Heap도 있구나)

그런데 퀵 같은 경우는 보통의 경우에는 Merge에 비해 훨씬 좋은 성능을 내지만
최악의 경우도 포함되어있을꺼라 생각하여 Merge 소트로 문제를 풀기로했다.

그리고 본인이 퀵보단 머지를 좋아한다.

소스 코드

class Solution {
    
    int[] sorted;
    
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int num1Length = nums1.length;
        int num2Length = nums2.length;
        
        int[] totalList = new int[num1Length+num2Length];
        sorted = new int[num1Length+num2Length];
        
        for(int i=0; i<num1Length; i++){
            totalList[i] = nums1[i];
        }
        
        for(int i=num1Length; i<num1Length+num2Length; i++){
            totalList[i]= nums2[i-num1Length];            
        }
        
        mergeSort(totalList,0,totalList.length-1);
        
        if(totalList.length%2==1)
            return totalList[totalList.length/2];
        else
            return (totalList[totalList.length/2] + totalList[totalList.length/2 - 1])/2.0;
        
    }
    
    public void mergeSort(int[] list,int left,int right){
        if(left<right){
            int mid=(left+right)/2;
            mergeSort(list,left,mid);
            mergeSort(list,mid+1,right);
            merge(list,left,mid,right);
        }
    }
    
    public void merge(int[] list,int left, int mid,int right){
        int i,j,k,l;
        i=left; j=mid+1; k=left;
        
        while(i<=mid && j<=right){
            if(list[i]<list[j])
                sorted[k++] = list[i++];
            else
                sorted[k++] = list[j++];
        }
        
        if(i<=mid){
            for(l=i; l<=mid; l++){
                sorted[k++]=list[l];
            }
        }else{
            for(l=j; l<=right; l++){
                sorted[k++] = list[l];
            }
        }
        
        for(int index=left; index<=right; index++){
            list[index]=sorted[index];
        }
        
    }
}

해결

대부분 퀵소트를 썼나보다 라는 생각을했다. 퀵 말고 더 효율적인 알고리즘을 사용한 것이 있을까 여기서??

Hard 정도의 난이도는 아닌 것 같다 (체감상) 😁