This is the 27th day of my participation in the August More Text Challenge

Leetcode -295- The median of the data stream

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

The median is the number in the middle of an ordered list. If the list length is even, the median is the average of the middle two numbers.

For example,

The median of [2,3,4] is 3

The median of [2,3] is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

Void addNum(int num) - Adds an integer from the data stream to the data structure. Double findMedian() - Returns the current median for all elements.Copy the code

Example:

AddNum (1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2Copy the code

Advanced:

  • How would you optimize your algorithm if all the integers in your data stream were in the range 0 to 100?
  • How would you optimize your algorithm if 99% of the integers in your data stream were in the range 0 to 100?

Related Topics

  • design
  • Double pointer
  • The data flow
  • The sorting
  • Heap (Priority queue)
  • 👍 👎 0 494

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Size root heap

  • The first thing to make clear is that the definition of median is location only
  • That is, it depends only on the middle element.
  • It is easy to think of defining two data structures of the same size or one element apart
  • Such a data structure needs to be able to output the largest or smallest elements in order of size
  • So the largest element in the first half, the smallest element in the second half
    • If odd, take the smallest element of one more element
    • If it is even, the average of the two data structures is taken
  • Such a data structure is easy to think of as a heap
  • And then update the median every time you add an element, and make sure it takes O(1) to get the median.
  • We define a big root heap, and a small root heap, where the small root heap stores the larger elements, and the large root heap stores the smaller elements
  • Ensure that the number of small root heap elements >= the number of large root heap elements
  • So we can figure out the median of even numbers
  • Let’s think about a couple of cases
    • The first one: the even case, where you add the elements and it becomes odd
    • We need to compare the added element with the top element of the big root heap
      • If it is larger than the top element of the large root heap, it can be directly added to the small root heap, and the median is the top element of the small root heap
      • Otherwise, take the top element of the big root heap, add the small root heap, put the added element into the big root heap, and take the top element of the small root heap as the median
    • The second is the technical case, where you add elements and you have an even number of elements
    • Basic train of thought is same with afore-mentioned circumstance
      • If it is larger than the top element of the large root heap, it can be directly added to the small root heap. The median is the average of the top elements of the two heaps
      • Otherwise, the top element of the large root heap is taken, the small root heap is added, the added element is put into the large root heap, and the median is the average of the top elements of the two heaps
PriorityQueue<Integer> minQ;
        PriorityQueue<Integer> maxQ;
        double mid;

        /** * initialize your data structure here. */
        public MedianFinder(a) {
            minQ = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    returno2 - o1; }}); maxQ =new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    returno1 - o2; }}); }public void addNum(int num) {
            if (maxQ.isEmpty()) {
                maxQ.add(num);
                mid = num;
                return;
            }
            if (minQ.isEmpty()) {
                int temp = maxQ.poll();
                minQ.add(Math.min(temp, num));
                maxQ.add(Math.max(temp, num));
                mid = ((double)maxQ.peek() +minQ.peek()) / 2;
                return;
            }
            // Have the same elements on both sides
            if (minQ.size() == maxQ.size()) {
                if (num < minQ.peek()) {
                    int temp = minQ.poll();
                    minQ.add(num);
                    maxQ.add(temp);
                } else {
                    maxQ.add(num);
                }
                mid = maxQ.peek();
            }
            // The two elements are different
            else {
                if (num < maxQ.peek()) {
                    minQ.add(num);
                } else {
                    int temp = maxQ.poll();
                    maxQ.add(num);
                    minQ.add(temp);
                }
                mid =  ((double)maxQ.peek() + minQ.peek()) / 2; }}public double findMedian(a) {
            return mid;
        }
Copy the code
  • Add elements: time complexity O(LGN); Take the median time complexity O(1)
  • Space complexity O(n)