My Java solution with merge the tow nums


  • 0
    C

    using the merge part of merge sort,if there has a sorted array,it is easy to find the median num.

    public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int[] totalNums = new int[nums1.length + nums2.length];
            int i = 0;
            int j = 0;
            int x = 0;
            while(i < nums1.length && j < nums2.length){
                if(nums1[i] > nums2[j]){
                    totalNums[x++] = nums2[j++];
                }else{
                    totalNums[x++] = nums1[i++];
                }
            }
            
            while(i < nums1.length){
                totalNums[x++] = nums1[i++];
            }
            while(j < nums2.length){
                totalNums[x++] = nums2[j++];
        }
            int mediaIndex = totalNums.length / 2;
            return totalNums.length % 2 == 0 ? (totalNums[mediaIndex] + totalNums[mediaIndex - 1]) / 2.0:totalNums[mediaIndex];
        }
    }

  • 0
    W
        no need complete  the merge
    
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int midPos = (nums1.length + nums2.length) / 2 + 1, curPos = 0;
        int i = 0, j = 0;
        double temp = 0, pre = 0;
        while (curPos < midPos && i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                pre = temp;
                temp = nums1[i++];
            } else {
                pre = temp;
                temp = nums2[j++];
            }
            curPos++;
        }
        while (curPos < midPos && i < nums1.length) {
            pre = temp;
            temp = nums1[i++];
            curPos++;
        }
    
        while (curPos < midPos && j < nums2.length) {
            pre = temp;
            temp = nums2[j++];
            curPos++;
        }
        return (nums1.length + nums2.length) % 2 == 1 ? temp : (pre + temp) / 2;
    }

  • 0
    F

    But the requirement is "The overall run time complexity should be O(log (m+n))." , this above solution may be O(m+n).


Log in to reply
 

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