295. The median of data streams

This is the 8th day of my participation in the August Text Challenge.More challenges in August

😀 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions! 🩲 warehouse address: a daily series

Title description:

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.

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?

Answer:

C++

Do not provide it on floating sand platforms

Method one: violence

Violent connection method: direct tail insertion, sort quick sort, take the median

class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<int> mem_num;
    MedianFinder() {}void addNum(int num) {
        this->mem_num.push_back(num);/ / insert
        sort(this->mem_num.begin(),this->mem_num.end());/ / fast row
    }
    
    double findMedian(a) {
        int len=this->mem_num.size(a);//cout<<len<<endl;
        double mid_num=0;
        if(len%2= =0){
            mid_num=(double(this->mem_num[len/2]) +double(this->mem_num[len/2- 1) /])2;
        }else if(len%2! =0){
            mid_num=double(this->mem_num[len/2]);
        }

        return mid_num;/ / the median}};Copy the code

Optimization: binary insertion, take the median

class MedianFinder {
public:
    /** initialize your data structure here. */
    vector<int> mem_num;
    MedianFinder() {}void addNum(int num) {
        auto addr=upper_bound(mem_num.begin(),mem_num.end(),num);
        mem_num.insert(addr,num);
    }
    
    double findMedian(a) {
        int len=this->mem_num.size(a);//cout<<len<<endl;
        double mid_num=0;
        if(len%2= =0){
            mid_num=(double(this->mem_num[len/2]) +double(this->mem_num[len/2- 1) /])2;
        }else if(len%2! =0){
            mid_num=double(this->mem_num[len/2]);
        }

        returnmid_num; }};Copy the code

Method 2: Priority queue

The data is divided into two priority queues (MIN and MAX) to record the number greater than the median and the number less than or equal to the median respectively. Each element in the priority queue has priority, and those with higher (or lower) priority will be the first to queue up, while those with the same priority will be queue up according to the order in the priority queue.

Priority queues are often implemented using a heap

If max.size ()> min.size (), max.top () is assigned to MIN. If max.size ()>MIN, max.top () is assigned to MIN. If max.size ()< min.size ()+1, optimize min.top () to MAX so that the queue heads of the two priority queues are in the median position. Returns the head of the queue, the median

STD ::priority_queue is implemented by default by the large root heap, i.e. the largest number is at the top of the heap, as shown below:

class MedianFinder {
public:
    priority_queue<int> MIN;
    priority_queue<int, vector<int>,greater<int>> MAX;

    MedianFinder() {}

    void addNum(int num) {
        if (MIN.empty() || num <= MIN.top()) {
            MIN.push(num);
            if (MAX.size() + 1 < MIN.size()) {
                MAX.push(MIN.top());
                MIN.pop();
            }
        } else {
            MAX.push(num);
            if (MAX.size() > MIN.size()) {
                MIN.push(MAX.top());
                MAX.pop(a); }}}double findMedian(a) {
        if (MIN.size() > MAX.size()) {
            return MIN.top(a); }return (MIN.top() + MAX.top/ ())2.0; }};Copy the code

Method three: ordered set + double pointer

Use multiset ordered set, and maintain two Pointers respectively to the left and right of the median two numbers, under the program pointer maintenance did not understand, can observe the example to understand;

class MedianFinder {
    multiset<int> nums;// Create an ordered set
    multiset<int>::iterator left, right;// Create a double pointer to the median

public:
    MedianFinder() : left(nums.end()), right(nums.end() {}void addNum(int num) {
        int n = nums.size(a);//n is the uninserted size
        nums.insert(num);// Insert data
        if(! n) {// The ordered set is empty and points to the head
            left = right = nums.begin(a); }else if (n & 1) {// check whether n is even or n is odd
            if (num < *left) {// Left and right are the same number, size() is even, and the new number is less than the left pointer, so left --;
                left--;
            } else {// The left pointer and the right pointer point to the same number, size() is even, the new number is larger than the left pointer point, so right++;right++; }}else {/ / n is even
            if (num > *left && num < *right) {// If size() is odd and size() is greater than and smaller than the number pointed to by the left pointer ++,right--, the left pointer points to the same place;
                left++;
                right--;
            } else if (num >= *right) {// If size() is odd and the new number is larger than the number pointed to by the right pointer, the left++ pointer points to the same place.
                left++;
            } else {Size () is odd, and the new number is smaller than the number pointed to by the left pointer.right--; left = right; }}}double findMedian(a) {
        return (*left + *right) / 2.0; }};Copy the code

JavaScript:

Mars Bird

Two heaps are used to store data streams
Use the smallest heap A to save the larger half and the largest heap B to save the smaller half
If the total length N is odd, the number of A is (N+1)/2 and the number of B is (n-1)/2
If the total length N is even, the number of A is N/2 and the number of B is N/2
Insert operation: if N is even, add an element to A, insert num into B, pop the top of B, insert A
Insert operation: if N is odd, add an element to B, insert num into A, pop the top of A, insert B
Median: can be obtained from the heap top elements of A and B, if N is odd, the median = the heap top of A; If N is even, the median =(the top of the heap of A + the top of the heap of B)/2

const MedianFinder = function () {
    // Default maximum heap
    const defaultCmp = (x, y) = > x > y;
    // Swap elements
    const swap = (arr, i, j) = > ([arr[i], arr[j]] = [arr[j], arr[i]]);
    // Heap class, default maximum heap
    class Heap {
        constructor(cmp = defaultCmp) {
            this.container = [];
            this.cmp = cmp;
        }
        / / insert
        insert(data) {
            const { container, cmp } = this;
            container.push(data);
            let index = this.size() - 1;
            while (index) {
                let parent = (index - 1) > >1;
                if(! cmp(container[index], container[parent])) {return; } swap(container, index, parent); index = parent; }}// Pop the top of the heap and return
        pop() {
            const { container, cmp } = this;
            if (!this.size()) {
                return null;
            }

            swap(container, 0.this.size() - 1);
            const res = container.pop();
            const length = this.size();
            let index = 0,
                exchange = index * 2 + 1;

            while (exchange < length) {
                // // In the case of the largest heap: if there is a right node and the value of the right node is greater than the value of the left node
                let right = index * 2 + 2;
                if (right < length && cmp(container[right], container[exchange])) {
                    exchange = right;
                }
                if(! cmp(container[exchange], container[index])) {break;
                }
                swap(container, exchange, index);
                index = exchange;
                exchange = index * 2 + 1;
            }

            return res;
        }
        // Get the heap size
        size() {
            return this.container.length;
        }
        // Get the heap top
        peek() {
            if (this.size()) return this.container[0];
            return null; }}/ / the minimum heap
    this.A = new Heap();
    / / the maximum heap
    this.B = new Heap((x, y) = > x < y);
};

MedianFinder.prototype.addNum = function (num) {
    if (this.A.size() ! = =this.B.size()) {
        When N is odd, we need to add an element to B
        // insert num into A; insert num into B
        this.A.insert(num);
        this.B.insert(this.A.pop());
    } else {
        // Add an element to A when N is even
        // insert num into B, then insert A into B
        this.B.insert(num);
        this.A.insert(this.B.pop()); }}; MedianFinder.prototype.findMedian =function () {
    // If the sum is even, return the average of the two heap tops
    // If the sum is odd, return the heap top of A
    return this.A.container.length === this.B.container.length
        ? (this.A.peek() + this.B.peek()) / 2
        : this.A.peek();
};
Copy the code

295. The median of data streams

295. The median of data streams

Title description:

Answer:

C++

Method one: violence

Method 2: Priority queue

Method three: ordered set + double pointer

JavaScript:

Related Posts

Embedded development xiaobai and Teacher Lian learn hello World of Hongmeng device development

Do programmers get paid by switching jobs?

AntV F2 pit crawl summary