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

Question

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

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

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

5 + 4 + 1 + 10 = 20

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

Answer 1

Псевдокод, найдите последний O (log 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++;
}

Используйте exponential_search для O (log N) для нахождения последнего и, следовательно, наибольшего значения.

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

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

Answer 2

Подсказка:

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

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

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