интервьюуличный срединный вызов

Задача Медиана M чисел определяется как 1) если M нечетное среднее число после сортировки их по порядку 2) если M - четное среднее число средних 2 чисел (опять же после сортировки) Сначала у вас есть пустой список номеров. Затем вы можете добавить или удалить какой-либо номер из списка. Для каждой операции добавления или удаления выведите медиану чисел в списке.

Пример. Для набора из m = 5 чисел {9, 2, 8, 4, 1} медианой является третье число в отсортированном наборе {1, 2, 4, 8, 9}, равное 4. Аналогично для набора m = 4, {5, 2, 10, 4} медиана представляет собой среднее значение второго и третьего элементов в отсортированном наборе {2, 4, 5, 10}, что равно (4+5)/2 = 4,5

Мой подход Я думаю, что проблема может быть решена таким образом.. Идея состоит в том, чтобы использовать предыдущее значение медианы и указатель для поиска нового значения медианы вместо пересчета при каждой операции добавления или удаления.

1) Используйте мультимножества, которые всегда сохраняют порядок элементов и допускают дублирование. Другими словами, как-то поддерживать отсортированный список.

2) Если операция добавить

2.1) Insert this element into set and then calculate the median

2.2) if the size of set is 1 then first element will be the median

2.3) if the size of set is even, then

           if new element is larger then prev median, new median will be avg of prev median

               and the next element in set.

           else new median will be avg of prev median and previous of prev element in the set.

2.4) if the size is odd, then

          if new element is larger then prev median

                 if also less then 2nd element of prev median ( 2nd element used to calculate avg

                    of prev median) then this new element to be added will be new median

                 else median will be 2nd element use to calculate the avg during last iteration prev

                    median.

          else

                 new median will be previous of prev median element in the set

3) Если операция удалить

3.1) First calculate the new median

3.2) If the size of set is 0 can't remove

3.3) If the size is 1 if the first element is the element to be removed, remove it else can't remove.

3.4) If the size of set is even, then

           if the element to be deleted is greater than or equal to 2nd element of prev median, then

               1st element of prev median will be new median

          else 2nd element of prev median will be the new median

3.5) If the size of set is odd, then

           if the element to be deleted is the prev median then find the avg of its prev and  next element.

           else if the element to be deleted is greater then prev median, new median will be avg of prev median and previous to prev median

           else median will be avg of prev median and next element to prev median.

3.6) Remove the element. 

Вот рабочий код... http://justprogrammng.blogspot.com/2012/06/interviewstreet- median-challenge.html.Что вы думаете об этом подходе?