Straightforward idea of merge sort. EASY to understand!


  • -1

    Using the idea of merge sort. Stack is used for the sake of easier to find the mid element.
    The time/space cost for this idea might not be the best, however, it's really straightforward and easier to understand.

    public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len1 = nums1.length;
            int len2 = nums2.length;
            boolean isEven = (len1+len2)%2==0;
            Stack<Integer> stack = new Stack<Integer>();
            int i1 = 0, i2 = 0;
            //saving current smaller element into stack,
            //till stack.size() > average number of elements --->find the mid point
            //and the stack.peek() 1 or 2 elements can be used for calculating the average for nums1 and nums2
            while(i1<len1||i2<len2){
                if(i1>=len1||i2>=len2){
                //nums1 or nums2 numbsers are running out
                    if(i1<len1) {
                        stack.push(nums1[i1]);
                        i1++;
                    }else{
                        stack.push(nums2[i2]);
                        i2++;
                    }
                }else{
                //push the smaller element in nums1[i1], nums2[i2]
                    if(nums1[i1]>nums2[i2]){
                        stack.push(nums2[i2]);
                        i2++;
                    }else{
                        stack.push(nums1[i1]);
                        i1++;
                    }
                }
                if(stack.size() > (len1+len2)/2){
                    if(isEven){//n is avg # of elements,  n-1 not in stack, n+1 in stack
                        return (stack.pop()+stack.pop())/2.0;
                    }else{// n not in stack, n+1 in stack
                        return stack.pop();
                    }
                }
            }
            return 0;
        }
    

  • 0
    R

    @davidthinkle.ding
    Hello,there is something that i don't understand,if the one is 4,5,6,the other one is 1,it should be4.5,isn't?but I get 5.5 ,so I want to ask Why? Isn't What I understand is wrong?


  • 0
    N

    @davidthinkle.ding Seems the time complexity to be O(m+n), rather than O(log(m+n))


Log in to reply
 

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