Some interesting follow up for this problem.

  • 0

    Actually this problem is very similar to one of the problem in my algorithm design class, here is the full version for it. Hope you are interested.

    1. Design a data structure that has the following properties (assume n elements 
    in the data structure, and that the data structure properties need to be preserved 
    at the end of each operation):
    • Find median takes O (1) time
    • Extract-Median takes O (log n ) time
    • Insert takes O (log n ) time
    • Delete takes O (log n ) time
    Do the following:
    (a) Describe how your data structure will work.
    (b) Give algorithms that implement the Extract-Median() and Insert() functions.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.