We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Hmmmm, I simply inserted each new number into an array in sorted order (as you would do in an insertion sort) and then used the array indexes to calculate the medians.
My reasoning was that since a print had to be done after each insertion, it would take linear time to print each result.
My maximum running time was 1.72 sec.
Now that I have seen the hints on how the min and max heaps should be used, I guess I should do it properly and see how it affects the running time.
EDIT: I have now re-written the solution using heaps as recommended. The maximum running time is now down to 0.06 sec.
Find the Running Median
You are viewing a single comment's thread. Return to all comments →
Hmmmm, I simply inserted each new number into an array in sorted order (as you would do in an insertion sort) and then used the array indexes to calculate the medians.
My reasoning was that since a print had to be done after each insertion, it would take linear time to print each result.
My maximum running time was 1.72 sec.
Now that I have seen the hints on how the min and max heaps should be used, I guess I should do it properly and see how it affects the running time.
EDIT: I have now re-written the solution using heaps as recommended. The maximum running time is now down to 0.06 sec.