Statement
Design a data structure that stores a dynamically changing list of integers and can find the median in constant time, MedianOfStream
with the following functionality:
Constructor(): Initializes an instance of the class.
insertNum(int num): Adds a new integer
num
to the data structure.findMedian(): Returns the median of all integers added so far.
Note: The median is the middle value in a sorted list of integers.
For an odd-sized list (e.g.,
), the median is the middle element: . For an even-sized list (e.g.,
), the median is the average of the two middle elements: .
Constraints:
num
, where num
is an integer received from the data stream.There will be at least one element in the data structure before the median is computed.
At most,
calls will be made to the function that calculates the median.