Алгоритм: найти индекс 2-го наименьшего элемента из неизвестного массива

Question

Я долго размышлял над своим домашним вопросом. Я приветствую (и предпочитаю) любые предложения или подходы к решению этой проблемы.

По сути, у меня есть массив A размера N. Мы не знаем элементов, но мы знаем, что они различны. Единственное, что у меня есть, это человек, который возьмет два индекса (i, j) в N. Этот человек скажет мне, является ли A [j] <или> A [i]. Я хочу найти алгоритм для нахождения индекса 2-го наименьшего элемента, задавая <= n + log n вопросов этому человеку. </p>

Answer 1

Этот ответ описывает, как найти второй по величине элемент; Нахождение второго наименьшего можно сделать аналогично. Для простоты мы также предполагаем, что все числа разные.

Чтобы найти величайший элемент, давайте построим дерево «чемпионата»: объединяем элементы в пары, решаем, какой из них больше (тот, кто является «победителем»), затем объединяем в пары победителей, решаем, что больше, и и так далее, пока вы не найдете «чемпиона», который является величайшим элементом. Это занимает n шагов. Теперь, второй по величине элемент должен быть по сравнению с чемпионом. (потому что только чемпион мог победить его). log n элементов были сравнены с чемпионом, поэтому из них выбираем наибольшее; это занимает log n шагов.

В качестве примера давайте посмотрим, как это работает для числового кортежа [6,4,3,5,2,1]. В первом раунде пары (6,4), (3,5), (2,1). Победителями становятся более крупные элементы в каждой паре, то есть 6,5,2. Во втором раунде пары - (6,5), 2. (у 2 здесь нет пары, поэтому он будет автоматически переведен в следующий раунд). Победители второго раунда - 6 и 2, в третьем раунде единственная пара - (6,2), 6 - победитель. Теперь, объединяя элементы в группы и выбирая победителя, мы создали (корневое, двоичное) дерево:

Это дерево обладает тем свойством, что для узла x и его дочерних элементов y,z у нас есть x>=y, x>=z, поэтому мы знаем, что самый большой элемент - тот, что вверху (в корне). Мы также знаем, что второй по величине элемент w не добрался до вершины, поэтому у него есть родительский элемент в дереве. Но его родительский элемент больше или равен w, поэтому на некотором уровне дерева один из дочерних элементов величайшего элемента - w. (Другими словами, второй величайший элемент может быть «побежден» только величайшим элементом). Поэтому все, что нам нужно сделать, - это вернуться на путь, по которому прошел величайший элемент, и собрать всех прямых детей, мы знаем, что среди них второй по величине. В нашем случае это элементы 2,5,4. (В общем, их около log n, где log обозначает основание два логарифма, потому что дерево имеет высоту log n.). Из этих элементов мы выбираем наибольшее с любым методом, который делает log n шагов, и мы нашли второй по величине.

Все это может напомнить нам о чемпионате, где цифры обозначают, насколько «хороша» каждая команда, отсюда и термин «дерево чемпионата».

Answer 2

Сначала найдите самый маленький элемент.Вы можете сделать это с n-1 сопоставлениями таким образом, чтобы каждый элемент сравнивался не более чем с log (n) другими элементами.Теперь посмотрите, какие элементы были сравнены с самым маленьким элементом, и найдите самый маленький из них.

Answer 3

unknown array = a[].
min1 = a[0].              first element.
min2 = 0.                 can equal anything

for(start at 0, until the end, grow by one):
    if(min1 > a[n]):
      min2 = min1.
      min1 = a[n].

return min2.

Answer 4

Легенда

S космическая сложность T Time Сложность

Я Арнаб Датта. Я говорю ... почему бы не пойти на:

1. maintain the elements as a MIN-HEAP array
                       [S = 0, 
                        T = O(n) if optimized <- ignore as its 1 time activity]
2. call deleteMin() 2 times 
                       [T <= h(tree_height) 
                                   - as internally deleteMin() calls shiftDown()]

итого T = O (ч)

Любой, у кого есть объяснение, почему это не лучше, чем использовать

     a. Tournament or
     b. using MAX-HEAP

Примечание: шаг 1 можно рассуждать о сложности пространства и времени.

Answer 5

1. Использовать 2 переменные - varSmallest и var2ndSmallest
2. Попросить человека сравнить 1-е и 2-е значение в массиве - установить меньший индекс для varSmallest, а другой - для var2ndSmallest
3. Взятьследующий индекс в последовательности и назовите его varIndexToCheck
4. Сравните значения varIndexToCheck и var2ndSmallest - если значение varIndexToCheck больше значения var2ndSmallest, перейдите к шагу 3
5. Сравните значения varIndexToCheck иесли значение varIndexToCheck больше значения varSmallest, установите var2ndSmallest = varIndexToCheck и перейдите к шагу 3
6. Остальное, установите var2ndSmallest = varSmallest и varSmallest = varIndexToCheck и затем перейдите к шагу 3 * 101 * * * * * *Повторяйте, пока нет больше индексов.После этого результирующий индекс находится внутри переменной var2ndSmallest и имеет сложность O (n log n)

Answer 6

Посмотрите на алгоритмы сортировки, такие как сортировка слиянием, которая в худшем случае имеет сложность O (n log n).«Лицо», говорящее вам, является ли A [j]> A [i] истинным или ложным, очевидно, является функцией сравнения.

Сортировка слиянием работает путем рекурсивного деления вашего массива на два меньших массива, в два раза меньше исходногомассив, затем применяя алгоритм сортировки слиянием к этим массивам снова.Если вы достигнете последнего шага из двух массивов только с одним элементом, вы попросите функцию «человек / сравнение» рассказать вам, как отсортировать эти массивы / элементы.Начиная с этого шага, вы начинаете объединять ваши подмассивы обратно в ваш оригинальный, но теперь отсортированный массив.

В конце вы можете просто вернуть второй элемент отсортированного массива, который является вторым наименьшим.

Answer 7

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

В этом случае вы можете начать с поиска наименьшего элемента из массива. Как бы вы это сделали?