Extremely!!!! concise and easy solution, java


  • -2
    P

    This algorithm works fine in [295H] Find Median from Data Stream.

    PriorityQueue<Integer> max = new PriorityQueue<>();
    PriorityQueue<Integer> min = new PriorityQueue<>(Collections.reverseOrder());
     
    public void addNum(int num){
        max.offer(num);
        min.offer(max.poll());
        
        if(max.size() < min.size()){
            max.offer(min.poll());
        }
    }
    
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1 == null && nums2 == null){
            return 0;
        }
        
        if(nums1.length == 0 && nums2.length == 0){
            return 0;
        }
        
        for(int num : nums1){
            addNum(num);
        }
        
        for(int num : nums2){
            addNum(num);
        }
        
        if(max.size() == min.size()){
            return (double) (max.peek() + min.peek())/2;
        }else{
            return max.peek();
        }
    }

  • 2
    Y

    I dont think this solution is O(log(m+n)) time complexity.


  • 0

    Looks like O(n log n + (n + m) log m) to me.


Log in to reply
 

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