[LeetCode] 4. Median of Two Sorted Arrays (Hard)

처음으로 푼 Hard 문제입니다. sorting된 두 개의 배열에서 median값을 찾아내는 문제입니다.

total index를 하나 두고, 두 개의 배열에서 더 작은 값을 비교하여 total index를 증가시켰습니다. total index가 중앙 index가 될 때, 해당 index의 값을 median값으로 구하였습니다.

현재 풀이는 시간복잡도가 O(m+n)인데, 해당 문제에서 요구하는 O(log(m+n))이 되는 다른 풀이도 추가할 예정입니다. O(log)가 되려면 바이너리 방식으로 비교해야 할 것 같습니다.

(문제에서 요구하는 시간복잡도를 충족하지 않는데도 pass가 되네요. 시간복잡도를 만족하지 않는 풀이는 사실상 난이도 Hard라고 보기는 어려울 것 같습니다ㅠㅠ. 처음 푼 Hard 문제가 생각보다 쉽길래 좋아했는데, 제대로 푼 게 아니었네요.) 

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        double median = 0.0;
        
        int medIdx = (m+n-1)/2;
        if((m+n)%2 == 1) // Median is one number
        {
            int i = 0;
            int j = 0;
            int totalIdx = 0;
            while(i<m || j<n)
            {
                if((i<m && j<n && nums1[i]<nums2[j]) || j>=n){
                    if(totalIdx == medIdx)
                    {
                        median = nums1[i];
                        break;
                    }
                    
                    totalIdx++;
                    i++;
                }
                else{
                    if(totalIdx == medIdx)
                    {
                        median = nums2[j];
                        break;
                    }
                    
                    j++;
                    totalIdx++;
                }
            }
        }
        else // Median is average of two numbers
        {
            int i = 0;
            int j = 0;
            int totalIdx = 0;
            while(i<m || j<n)
            {
                if( (i<m && j<n && nums1[i]<nums2[j]) || j>=n){
                    if(totalIdx == medIdx)
                    {
                        median += nums1[i] /2.0;
                    }
                    else if(totalIdx == medIdx + 1)
                    { 
                        median += nums1[i] /2.0;
                        break;
                    }
                    
                    totalIdx++;
                    i++;
                }
                else{
                    if(totalIdx == medIdx)
                    {
                        median += nums2[j] /2.0;
                    }
                    else if(totalIdx == medIdx + 1)
                    {
                        median += nums2[j] /2.0;
                        break;
                    }
                    
                    j++;
                    totalIdx++;
                }
            }
            
        }
        return median;
    }
};