Design a data structure that continuously receives integers and can report the median of all numbers that have been added so far, on demand.
For an odd number of collected values, the median is the middle element when sorted. For an even count, the median is the arithmetic mean of the two middle elements (i.e., their sum divided by two).
The structure must expose two methods:
addNum(x): records the integer x.findMedian(): returns the current median. The return value should be treated as a floating‑point number, but when the result is an exact integer you may print it without a fractional part (see output format).Follow‑up: Modify the design so that it can also answer arbitrary percentile queries: findPercentile(p) with p an integer between 0 and 100 inclusive. Use the nearest‑rank rule: for n sorted elements, the p‑th percentile is the element at index ceil(p / 100 * n) - 1 (using 0‑based indexing). When p = 0, return the smallest value. Discuss how to keep operations efficient while supporting these additional queries.
Implement processOperations(operations), where operations is a list of strings, each one an operation – either:
add x (insert integer x), ormedian (report the median of all inserted numbers so far).There will always be at least one add before any median command.
Return a list with the median (as a float) for every median query, in order. In the example outputs below, a whole-number median is shown as an integer, and any other median with exactly one digit after the decimal point (e.g., 5.5).
Example 1:
Input:
6
add 3
add 8
median
add 10
median
median
Output:
5.5
8
8
Explanation: After the first two insertions, the sorted list is [3, 8]; median = (3 + 8) / 2 = 5.5. Adding 10 yields a sorted order of [3, 8, 10]; the middle element is 8. The second and third median queries both return 8.
Constraints:
1 ≤ q (number of operations) ≤ 200,000addNum and findMedian as fast as possible (ideally O(log n) for insertion and O(1) for median retrieval, where n is the current number of elements).Input:
6
add 1
add 2
median
add 3
median
median
Output:
1.5
2
2