Какой самый быстрый алгоритм поиска списка с именами и номерами

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

a 1, a 4, a 5, b 0, b 4, c 1, n 9, n 10

Мне нужно было бы выложить

5 + 4 + 1 + 10 = 20

Мне нужно сделать это за время O (войти).

Похоже на домашнее задание, которое нужно делать самостоятельно

Jens 10.09.2018 08:32

Вы не можете отсортировать элементы n во времени O(log n), поскольку проверка всех элементов уже будет иметь сложность O(n). Если вам нужна сложность O(n * log n), то алгоритмов подгонки довольно много. Просто посмотрите их и используйте тот, который вам нравится.

Thomas 10.09.2018 08:32

Сначала - что такое?

MBo 10.09.2018 08:37

Вы не можете сделать это за логарифмическое время. В худшем случае каждое имя имеет только одно число, поэтому вам придется сложить их все: вы не можете добавить n произвольных чисел за сублинейное время.

Andy Turner 10.09.2018 08:51

O (logn) возможно только в том случае, если у вас есть дополнительное ограничение на количество разных имен в вашем списке. Если количество разных имен (близко к) logn, вы можете построить алгоритм, который в среднем будет O (logn) (используя знание того, как сортируется список)

Erwin Bolwidt 10.09.2018 10:14

Если вы уже знаете имена в списке, просто возьмите верхнюю границу для каждого из имен. Это лучшее, что вы можете сделать, и он выполняется за O (M * log (N)), где M - количество имен, а N - общее количество элементов в списке.

Andrew Scott 10.09.2018 11:48
6
6
1 127
2

Ответы 2

Намекать:

Отсканируйте список, сохраняя «наибольшее число в текущем прогоне» и «накопитель для суммы». Каждый раз, когда элемент отличается от предыдущего, накапливайте текущее наибольшее число и сбрасывайте его до значения элемента.

Я позволяю вам позаботиться о правильной инициализации и финализации.

Это Θ (n), и вы не можете сделать это быстрее. В худшем случае, если все имена разные, вам нужно вывести сумму всех чисел, а это невозможно сделать, не прочитав их все (как сказал Энди).

Псевдокод, найдите последний O (журнал N) каждого имени O (M).

auto it = vec.begin();
while (it != vec.end()) { // O(M)
  auto last = find_last_with_same_name(it, it->name); 
  sum += last.value;
  it++;
}

Используйте экспоненциальный_поиск для O (log N) для поиска последнего и, следовательно, наибольшего значения.

Всего O (M log N).

Если M, количество имен является константой, вы получите O (log N), но для этого потребуются некоторые юридические правила.

Другие вопросы по теме