Java solution-4ms(Sacrifice space)


  • 0
    Y

    Although the code has a high degree of spatial complexity,it is enough simple.

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

  • 0
    C

    Are you sure it's 4ms? My implementation is exactly like yours and takes 60ms


  • 0
    Y

  • 0
    L

    I run the same code and got 71 ms :(


  • 1
    S

    The merge requires O(m+n) time complexity while the problem asks for O(log(m+n)). @YuanCode


  • 0
    G

    I don‘’t konw how to O(log(M+N))


Log in to reply
 

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