Find Median From Data Stream Java Solution
📖Blog ："LeetCode 295. Median Data Flow-JavaScript"
🐱Github ：https://github.com/dongyuanxin/blog
Title description: The median is the number in the middle of the ordered list. If the length of the list is even, the median is the average of the middle two numbers.
Design a data structure that supports the following two operations:
-
void addNum(int num)Add an integer from the data stream to the data structure. -
double findMedian()Returns the median of all current elements.
Solution 1: Violence
Every time the median is taken out, all elements are sorted first, and then the median is calculated. code show as below:
// Original address: https://xxoo521.com/2020-02-27-find-median-from-data-stream/ var MedianFinder = function() { this.data = []; }; MedianFinder.prototype.addNum = function(num) { this.data.push(num); }; MedianFinder.prototype.findMedian = function() { const length = this.data.length; if (!length) { return null; } this.data.sort((a, b) => a - b); const mid = Math.floor((length - 1) / 2); if (length % 2) { return this.data[mid]; } return (this.data[mid] + this.data[mid + 1]) / 2; }; You can also sort directly when adding elements. The time complexity is the same, both are\(O(NlogN)\)，Unable to ac。
Solution 2: Binary search
In fact, there is no need to reorder all elements every time you add elements. If you have always ensured that the elements are in order, when you add a new element, you only need to insert the element to the correct position. Finding the correct position can be done by "binary search".
In order to ensure the order of the previous elements, put them in the correct position for each newly added element.
The code is implemented as follows:
// ac address: https://leetcode-cn.com/problems/find-median-from-data-stream/ // Original address: https://xxoo521.com/2020-02-27-find-median-from-data-stream/ var MedianFinder = function() { this.data = []; }; MedianFinder.prototype.addNum = function(num) { if (!this.data.length) { this.data.push(num); return; } let left = 0, right = this.data.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); if (this.data[mid] === num) { this.data.splice(mid, 0, num); return; } else if (this.data[mid] < num) { left = mid + 1; } else { right = mid - 1; } } this.data.splice(right + 1, 0, num); }; MedianFinder.prototype.findMedian = function() { const length = this.data.length; if (!length) { return null; } const mid = Math.floor((length - 1) / 2); if (length % 2) { return this.data[mid]; } return (this.data[mid] + this.data[mid + 1]) / 2; }; Need for binary search\(O(logN)\)The complexity of moving elements requires\(O(N)\)Complexity, so the time complexity is\(O(N)\)。
Solution 3: Maximum heap + minimum heap
For this kind of dynamic data, the heap is an excellent solution. Prepare two heaps:
- Maximum heap: store the smaller half of the elements in the data stream
- Minimal heap: store the larger half of the elements in the data stream
It is necessary to ensure the "balance" of these two heaps. The balance here means: the size of the largest heap = the size of the smallest heap, or the size of the largest heap = the size of the smallest heap + 1.
When calling findMedian to query the median, the median is the top element of the largest heap, or (top element of the largest heap + top element of the smallest heap)/2
The remaining question is how to ensure the balance of the heap? Proceed as follows:
- Let num enter maxHeap first
- Take the top element of maxHeap and put it in minHeap
- If this time
The size of the largest heap <the size of the smallest heap, Take out the top element of minHeap and let in maxHeap
Since there is no heap in JavaScript, you have to implement it yourself.In the implementation, only one copy of the heap code is needed, and the comparison function for judgment in the heap can be passed in from the outside world.. This is a design pattern called "Bridge Mode". You can read this article for details:"Design Pattern-Bridge Mode-JavaScript"
// ac address: https://leetcode-cn.com/problems/find-median-from-data-stream/ // Original address: https://xxoo521.com/2020-02-27-find-median-from-data-stream/ const defaultCmp = (x, y) => x> y; // The default is the maximum heap const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]); class Heap { /** * The default is the maximum heap * @param {Function} cmp */ constructor(cmp = defaultCmp) { this.container = []; this.cmp = cmp; } insert(data) { const { container, cmp } = this; container.push(data); let index = container.length - 1; while (index) { let parent = Math.floor((index - 1) / 2); if (!cmp(container[index], container[parent])) { return; } swap(container, index, parent); index = parent; } } extract() { const { container, cmp } = this; if (!container.length) { return null; } swap(container, 0, container.length - 1); const res = container.pop(); const length = container.length; 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; } top() { if (this.container.length) return this.container[0]; return null; } } The overall code logic is as follows:
// ac address: https://leetcode-cn.com/problems/find-median-from-data-stream/ // Original address: https://xxoo521.com/2020-02-27-find-median-from-data-stream/ var MedianFinder = function() { this.maxHeap = new Heap(); this.minHeap = new Heap((x, y) => x < y); }; MedianFinder.prototype.addNum = function(num) { this.maxHeap.insert(num); this.minHeap.insert(this.maxHeap.top()); this.maxHeap.extract(); if (this.maxHeap.container.length < this.minHeap.container.length) { this.maxHeap.insert(this.minHeap.top()); this.minHeap.extract(); } }; MedianFinder.prototype.findMedian = function() { return this.maxHeap.container.length > this.minHeap.container.length ? this.maxHeap.top() : (this.maxHeap.top() + this.minHeap.top()) / 2; }; The time complexity is\(O(logN)\), The space complexity is\(O(N)\)。
👇Scan QR code to follow"Heart Tan Blog", Check the "front-end graph" & "algorithm problem solution", insist on sharing and grow together👇
Leetcode brushing note 295 median data stream
Leetcode brushing note 295 median data stream source address:295. Medium number of data streams Problem Description: The median is the number in the middle of the ordered list. If the list length is e...
295. Find Median from Data Stream
topic: Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examples: [2,3,4] ...
295. Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. For example, [2,3,4], the median is...
295. Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examples: [2,3,4] , the ...
Find Median from Data Stream 295
Topic link:https://leetcode.com/problems/find-median-from-data-stream/ Title description: Design a class with two operations void addNum(int num) - Add a integer number from the data stream to ...
295. Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. Examples: [2,3,4] , the ...
295. Find Median from Data Stream
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. For example, [2,3,4], the median is...
Find Median From Data Stream Java Solution
Source: https://www.programmerall.com/article/2100387309/