Is my solution O(log(m+n)) or O(m+n)?


  • 0
    H
    public static double findMedianSortedArrays(int A[], int B[]) {
    
    	ArrayList<Integer> a = new ArrayList<Integer>(); 
    	for	(int i : A){
    		a.add(i);
    	}
    	ArrayList<Integer> b = new ArrayList<Integer>(); 
    	for	(int i : B){
    		b.add(i);
    	}
    
    	ArrayList<Integer> c = new ArrayList<Integer>();
    	ArrayList<Integer> res = merge(a, b, c);
    
    	if (res.size() % 2 == 0)
    		return ((double)(res.get(res.size()/2 - 1) + res.get(res.size()/2))) / 2;
    	else
    		return res.get(res.size()/2);
    
    }
    
    public static ArrayList<Integer> merge(ArrayList<Integer> a, ArrayList<Integer> b, ArrayList<Integer> c){
    	
    
    	while(a.size() > 0 || b.size() > 0){
    		if (a.size() > 0 && b.size() > 0){
    			if (a.get(0) <= b.get(0)){
    				c.add(a.get(0));	
    				a.remove(0);
    				merge(a, b, c);
    			}
    			else {
    				c.add(b.get(0));
    				b.remove(0);
    				merge(a, b, c);
    			}			
    		}
    		else if (a.size() > 0 ){
    			c.add(a.get(0));	
    			a.remove(0);
    			merge(a, b, c);
    		}
    		else if (b.size() > 0){
    			c.add(b.get(0));
    			b.remove(0);
    			merge(a, b, c);
    		}
    	}
    
    	return c;
    }
    

    I used the merge part the merge sort after converting the int [] to ArrayList<Integer>


  • 4
    S

    First of all, merging two sorted arrays is at best an O(m+n) operation, you can't do better than that. if your code replies on merge, than it is guaranteed that it can not be faster than O(m+n).

    Your merge function can be improved: you can merge two arrays using a loop, or using recursion, but it is pointless to use both.

    Even without merging, the copying from A, B to a,b already costs O(m+n), so you don't even need to see the rest before you can tell it is not a O(log(m+n)) solution, to say the least.

    An O(log n) solution should not involve copying an entire array, and you must use some sort of binary search.


Log in to reply
 

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