Как вычислить медиану Карты <Интервал, Интервал>?

Линейное время

Если вам известна сумма чисел (в вашем случае это 16), вы можете перейти от начала или до конца карты и суммировать счетчики, пока не получите перейти к округлению (n / 2) -го элемента, или в случае, если сумма четна к среднему значению минимального (n / 2) -го и ceil (n / 2) -го элементов = медианы .

Если вы не знаете общий счет, вам придется пройти их все хотя бы один раз.

Сублинейное время

Если вы можете выбрать структуру данных и выполнить предварительную обработку, см. Википедию по алгоритму выбора , и вы можете получить даже сублинейный алгоритм. Вы также можете получить сублинейное время, если знаете что-то о распределении данных.

РЕДАКТИРОВАТЬ: Итак, в предположении, что у нас есть последовательность со счетчиками, мы можем сделать следующее:

• при вставке пары ключ -> счетчик поддерживать другую карту - ключ -> running_total
• таким образом вы будете иметь структуру, в которой вы сможете получить total_count, посмотрев на running_total последнего ключа
• и , вы сможете выполнить двоичный поиск, чтобы найти элемент, где текущая сумма близка к total_count / 2

Это удвоит использование памяти, но даст производительность O (log n) для медианы и O (1) для total_count.

• Использовать SortedMap , то есть TreeMap
• Проходить по карте один раз, чтобы вычислить общее количество элементов, то есть сумму всех вхождений
• Повторите еще раз и суммируйте вхождения, пока не дойдете до половины от общего числа. Число, которое привело к тому, что сумма превысила половину общей суммы, является медианным значением
• . Тестирование на предмет единичных ошибок.

Для простого, но, возможно, не очень эффективного алгоритма, я бы сделал это так:

1. развернуть карту в список.

практически сказано: перебрать карту и добавить ключ «значение-время» в новый список. Наконец отсортируйте список.

//...
List<Integer> field = new ArrayList<Integer>();
for (Integer key:map) {
  for (int i = 0; i < map.get(key); i++) {
    field.add(key);
  }
}
Collections.sort(field);

2. вычислить медиану

, теперь вам нужно реализовать метод int calculateMedian (List sorted) . Это зависит от того, какой тип медианы вам нужен. Если это просто медиана выборки, то результатом будет либо самое среднее значение (для списков с нечетным числом элементов), либо среднее из двух крайних средних значений (для списков с четной длиной). Учтите, что список нужно отсортировать!

(Ссылка: Sample Median / wikipedia )

Хорошо, хорошо, хотя Крис не упомянул об эффективности, вот идея, как вычислить среднюю выборку (!) Без расширения карты. ..

Set<Integer> sortedKeys = new TreeSet<Integer>(map.keySet()); // just to be sure ;)
Integer median = null;  // Using Integer to have a 'invalid/not found/etc' state
int total = 0;
for (Integer key:sortedKeys) {
  total += map.get(key);
}
if (isOddNumber(total)) { // I don't have to implement everything, do I?
  int counter = total / 2;  // index starting with 0
  for (Integer key:sortedKeys) {
    middleMost -= map.get(key);
    if (counter < 0) {
      // the sample median was in the previous bin
      break;
    }
    median = key;
  }
} else {
  int lower = total/2;
  int upper = lower + 1;
  for (Integer key:sortedKeys) {
    lower -= map.get(key);
    upper -= map.get(key);
    if (lower < 0 && upper < 0) {
      // both middlemost values are in the same bin
      break;
    } else (lower < 0 || upper < 0) {
      // lower is in the previous, upper in the actual bin
      median = (median + key) / 2; // now we need the average
      break;
    }
    median = key;
  }
}

(Компилятора у меня под рукой нет - если в нем много синтаксических ошибок, относитесь к нему как к псевдокоду;))

Использование Guava:

Multiset<Integer> values = TreeMultiset.create();
Collections.addAll(values, 1,1,2,2,2,2,3,3,3,4,5,6,6,6,7,7);

Теперь ответ на ваш вопрос:

return Iterables.get(values, (values.size() - 1) / 2);

Действительно. Вот и все. (Или проверьте равномерность размера и усредните два центральных значения, чтобы быть точным.)

Если подсчеты особенно велики, было бы быстрее использовать entrySet мультисета и вести текущую сумму, но самый простой способ обычно подходит.