Two Pointers
Design
Sorting
Heap (Priority Queue)
Data Stream
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
Implement a class that supports adding integers from a data stream one at a time and finding the median of all elements added so far.
For example:
- `addNum(num)` adds an integer to the data structure.
- `findMedian()` returns the median of all elements so far.
Example 1
Input: addNum(1), addNum(2), findMedian()
Output: 1.5
Example 2
Input: addNum(1), addNum(2), addNum(3), findMedian()
Output: 2.0
Example 3
Input: addNum(1), addNum(2), addNum(3), addNum(4), findMedian()
Output: 2.5
Constraints
- •
-10⁵ <= num <= 10⁵ - •
There will be at least one element in the data structure before findMedian is called. - •
At most 5 * 10⁴ calls will be made to addNum.
Time Complexity
O(log n) add, O(1) query