Sword finger offer 40.41 Sort (medium)

40.

subject :

The finger of the sword Offer 40. The smallest k Number https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

idea : Prioritize , Back again .

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] res = new int[k];
        for(int i=0;i<arr.length;i++){
            if(k-->0)
                res[i]=arr[i];
        }
        return res;
    }
}

result :

 

41.

The finger of the sword Offer 41. Median in data stream https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/

idea : Think of bubbling , choice , Heap sorting can be used to sort the elements to one final position each time , Use bubble sort to find half of bubbles each time , But the result timed out .

idea : You can use heap sort , Faster .

In fact, it's not just fast , You can use two heaps , The big top pile stores the smaller half , The small top stack stores half the larger number , And make the length of the big top pile >= Small cap pile , Equal length , Put it in the big top pile , In this way, parity can be determined first , Then get the median by getting the value of one or two heap tops .

Code :

class MedianFinder {
    Queue<Integer> A, B;// Use priority queues ( Default small top heap , The large top heap needs to customize the comparison criteria )
    public MedianFinder() {
        A = new PriorityQueue<>(); //  Small cap pile , Save the larger half 
        // B = new PriorityQueue<>((x, y) -> (y - x)); //  Big pile top , Save the smaller half 
        B = new PriorityQueue<>(Comparator.reverseOrder()); //  Big pile top , Save the smaller half 
    }
    public void addNum(int num) {
        if(A.size() > B.size()) { // before , Odd length  ->  Add to B in , Make even  A The length of =B The length of 
            A.add(num);
            B.add(A.poll());
        } else { // before , The length is even  ->  Add to A in , Make odd  A The length of >B The length of 
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() > B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}


/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

result :