Нахождение наибольшего и второго по величине из N чисел

Question

Учитывая n чисел, как мне найти наибольшее и второе по величине число, используя не более n + log (n) сравнений?

Обратите внимание, что это не O (n + log (n)), а сравнение n + log (n).

Answer 1

Пейтон дал комментарий.

Позвольте мне уточнить.

Как сказал Пейтон, это можно сделать путем выбора турнира.

Думайте об этом как о сингле сингловтеннисный турнир, где способности игроков имеют строгий порядок, а исход матча определяется исключительно этим порядком.

В первом раунде люди выбывают.В следующем раунде другая половина и т. Д. (С некоторыми возможными пока).

В конечном итоге победитель определяется в последнем и последнем раунде.

Это можно рассматривать как дерево.

Каждый узел дерева будет победителем матча между потомками этого узла.

Листья - это игроки.Победителем первого раунда являются родители листьев и т. Д.

Это полное двоичное дерево на n узлах.

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

Победитель определяется в n-1 матчах (вы выбиваете по одному на матч), а победитель среди logn определяется в logn -1 матчах.

Таким образом, вы можете выбрать самый большой ивторое по величине в n + logn - 2 сравнения.

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

Чтобы доказать, что предполагается система очков, в которой после матча победитель получает очки проигравшего.Первоначально все начинаются с 1 очка.

В конце у финального победителя есть n баллов.

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

Answer 2

Есть ли проблема с этим? Это не более 3n сравнений (не считая сравнения i < n). Если считать это, то это 4n (или 5n во втором примере).

double first = -1e300, second = -1e300;
for (i = 0; i < n; i++){
  if (a[i] > first){
    second = first;
    first = a[i];
  }
  else if (a[i] > second && a[i] < first){
    second = a[i];
  }
}

другой способ его кодирования:

for (i = 0; i < n; i++) if (a[i] > first) first = a[i];
for (i = 0; i < n; i++) if (a[i] < first && a[i] > second) second = a[i];