Обход массива, чтобы найти второй по величине элемент в линейном времени

Question

Есть ли способ в линейном времени, с помощью которого мы можем найти, который является вторым по величине элементом массива? Элементы массива могут быть положительными, отрицательными или нулевыми. Элементы могут быть повторяющимися. STL не допускаются. Python можно использовать.

Решение: отсортировать массив и взять второй элемент, но Сортировка не разрешена

Модификация: По определению вторым по величине элементом будет элемент, который численно меньше. Например, если у нас есть

Arr = {5,5,4,3,1} Тогда второй по величине 4

Добавление Скажем, если я хочу обобщить вопрос до kth наибольшего и сложность меньше, чем линейная, как nlogn, что может быть решением.

Answer 1

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

.... есть что-нибудь хитрое в этом вопросе, которого я не вижу?

Answer 2

Вы можете, это псевдоалгоритм:

max = 2max = SMALLEST_INT_VALUE;

for element in v:
   if element > max:
      2max = max;
      max = element;

  else if element > 2max:
      2max = element;

2max - это значение, которое вы ищете.

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

Answer 3

Если вам нужен истинный алгоритм O (n), и вы хотите найти n-й по величине элемент в массиве, тогда вы должны использовать quickselect (это в основном быстрая сортировка, где вы выбрасываете раздел, который вам не интересен), и ниже отличная рецензия с анализом времени выполнения:

http://pine.cs.yale.edu/pinewiki/QuickSelect

Answer 4

Псевдокод:

int max[2] = { array[0], array[1] }

if(max[1] < max[0]) swap them

for (int i = 2; i < array.length(); i++) {
  if(array[i] >= max[0]) max[1] = max[0]; max[0] = array[i]
  else if(array[i] >= max[1]) max[1] = array[i];
}

Теперь массив max содержит максимум 2 элемента.

Answer 5

• создать временный массив размером 3
• скопируйте туда первые 3 элемента,
• сортировка временного массива,
• заменить последний во временном массиве на 4-й элемент из исходного массива,
• сортировка временного массива,
• заменить последний во временном массиве на 5-й элемент из исходного массива,
• сортировка временного массива,
• и т.д.

Сортировка массива размером 3 - это постоянное время, и вы делаете это один раз для каждого элемента исходного массива, следовательно, общее линейное время.

Answer 6

// assuming that v is the array and length is its length
int m1 = max(v[0], v[1]), m2 = min(v[0], v[1]);

for (int i=2; i<length; i++) {
  if (likely(m2 >= v[i]))
    continue;
  if (unlikely(m1 < v[i]))
    m2 = m1, m1 = v[i];
  else
    m2 = v[i];
}

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

Answer 7

Да. Вы пометили это как C / C ++, но упомянули, что можете сделать это на Python. Во всяком случае, вот алгоритм:

1. Создать массив (очевидно).
2. Если первый элемент больше второго, установите первую переменную для первого элемента, а вторую переменную для второго элемента. В противном случае сделайте наоборот.
3. Переберите все элементы (кроме первых двух).
4. Если элемент из массива больше первой переменной, установите вторую переменную равной первой переменной, а первую переменную - элементу. Иначе, если элемент больше второй переменной, установите вторую переменную для элемента.

Вторая переменная - ваш ответ.

list = [-1,6,9,2,0,2,8,10,8,-10]

if list[0] > list[1]:
        first = list[0]
        second = list[1]
else:
        first = list[1]
        second = list[0]

for i in range(2, len(list)):
        if list[i] > first:
                first, second = list[i], first
        elif list[i] > second:
                second = list[i]

print("First:", first)
print("Second:", second)

Answer 8

Я думаю, что другие ответы не учитывают тот факт, что в массиве, подобном [0, 1, 1], второй по величине равен 0 (согласно обновленному определению проблемы). Кроме того, все упоминания о быстром отборе не O (n), а скорее O (n ^ 2) и выполняют гораздо больше работы, чем необходимо (помимо всего прочего это алгоритм сортировки, запрещенный в заявлении задачи). Вот алгоритм, очень похожий на алгоритм Симоны, но обновленный и возвращающий второй по величине уникальный элемент:

def find_second(numbers):
    top = numbers[0]
    second = None

    for num in numbers[1:]:
        if second is None:
            if num < top: second = num
            elif num > top:
                second = top
                top = num
        else:
            if num > second:
                if num > top:
                    second = top
                    top = num
                elif num < top: second = num

    if second is not None: return second
    return top

if __name__ == '__main__':
    print "The second largest is %d" % find_second([1,2,3,4,4,5,5])