Sword finger Offer 41 Median in data stream

It's really a difficult question 😂, It's really a little difficult. At first, I thought it was violent. I always use sort every time I ask for mid, but as we all know, the time complexity of sort is \ (O(nlogn) \), and it will call mid multiple times, so this method is not used here.
In addition, you can find a way to define a super large arr during insertion, find the position where num should be inserted and insert it every time. The average time complexity is \ (O(n) \), which has been improved a lot.
The idea is to find the insertion position in two or by insertion sorting. The code is as follows:

class MedianFinder {
    private int size;
    private int[] arr;
    /** initialize your data structure here. */
    public MedianFinder() {
        this.size = 0;
        this.arr = new int[50010];
    }
    
    public void addNum(int num) {
        // Insert sort finds where num should be inserted
        int idx = this.size - 1;
        // At this time, there are size elements, and the index position should start from size - 1
        while(idx >= 0) {
            if(this.arr[idx] >= num) {
                idx--;
                continue;
            } else if(this.arr[idx] < num) {
                break;
            }
        }
        // In order to find the first place where the index should be greater than id num, it should start from the first place where the index should be inserted++
        idx++;
        // move backward 
        for(int i = size; i > idx; i--) {
            this.arr[i] = this.arr[i - 1];
        }
        // Set value
        this.arr[idx] = num;
        this.size++;
    }
    
    public double findMedian() {
        if(this.size % 2 == 1) {
            return this.arr[this.size / 2] * 1.0;
        } else {
            return (this.arr[this.size / 2 - 1] + this.arr[this.size / 2]) / 2.0;
        }
    }
}

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

The binary approach is similar, but it optimizes the search process from \ (O(n) \) to \ (O(logn) \), but in fact, the time complexity depends on the rearrangement process, so the impact is not great.

The next step is the double pile method, which is too slow 😂, This topic creates two heaps, one is the small root heap and the other is the large root heap. Always make the size of the two heaps no more than 1. Here, for convenience, we make the large root heap 1 larger than the small root heap.
Next, we analyze that we store the smaller half of the array in the large root heap and the larger step in the small root heap, so that we can easily get the intermediate value. 😂
The next thing to consider is the heap order, because I assume that the number of large root heap is at most one more than that of small root heap. Therefore, when the two sizes are the same, it is necessary to fill the large root heap with numbers. However, it should be noted here that we need to ensure that all the numbers in the small root heap are greater than that in the large root heap, so put num into the small root heap first, Next, put the smallest out of the small root heap into the large root heap, so as to ensure that it is an accurate intermediate value. The same is true for the insertion process of the small root heap.

class MedianFinder {

    // Large top pile
    private PriorityQueue<Integer> pq1;
    // Small top pile
    private PriorityQueue<Integer> pq2;


    /** initialize your data structure here. */
    public MedianFinder() {
        this.pq1 = new PriorityQueue<>((a, b) -> b - a);
        this.pq2 = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // So that the number of large root heaps is always greater than or equal to 1 than the number of small root heaps
        if((pq1.size() + pq2.size()) % 2 == 0) {
            // The size of the two heaps is equal, and the number of large root heaps needs to be increased. However, in order to maintain the balance, it is necessary to put them into the small root heap first, and then take out the smallest one and put it into the large root heap
            pq2.offer(num);
            pq1.offer(pq2.poll());
        } else {
            // One of the two heaps is larger and the other is smaller. It is necessary to increase the number of small root heaps. Similarly, it is necessary to put the large root heap first and put the largest one back into the small root heap
            pq1.offer(num);
            pq2.offer(pq1.poll());
        }
    }
    
    public double findMedian() {
        if(pq1.size() - pq2.size() == 1) {
            return pq1.peek() * 1.0;
        } else {
            return (pq1.peek() + pq2.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();
 */