If I use merge sort to solve this problem, does that belong to log(m+n)? java


  • -4
    R
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int[] mergeNums = merge(nums1,nums2);
            int len = mergeNums.length;
    
            double median = 0.0;
            if(len % 2 == 0){
                median = ((double)mergeNums[(len - 1) / 2] + (double)mergeNums[(len - 1) / 2 + 1]) / 2;
            }else{
                median = (double)mergeNums[(len - 1) / 2];
            }
            return median;
        }
        
        public int[] merge(int[] nums1, int[] nums2){
            int curr = 0;
            int len1 = nums1.length, len2 = nums2.length;
            int[] newNums = new int[len1 + len2];
            int start1 = 0, end1 = len1-1, start2 = 0, end2 = len2 - 1; 
            while(start1 <= end1 && start2 <= end2){
                if(nums1[start1] < nums2[start2]){
                    newNums[curr] = nums1[start1];
                    curr++;
                    start1++;
                }else{
                    newNums[curr] = nums2[start2];
                    curr++;
                    start2++;
                }
            }
            
            while(start1 <= end1){
                newNums[curr] = nums1[start1];
                curr++;
                start1++;
            }
            
            while(start2 <= end2){
                newNums[curr] = nums2[start2];
                curr++;
                start2++;
            }
            
            return newNums;
        }

  • 0
    Z

    I did the same solution, didn't see that Log sign..


  • 2
    H

    No, because when merging you have to iterate through all the elements of both arrays, so it would be O(m+n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.