Блог

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

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

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

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

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

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

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

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

 max = 2max = SMALLEST_INT_VALUE;

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

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

2max — это искомое значение.

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

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

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

Псевдокод:

 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];
}
  

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

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

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

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

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

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

 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)
  

 // 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];
}
  

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

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

 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])
  

 // Second larger element and its position(s)
    int[] tab = { 12, 1, 21, 12, 8, 8, 1 };
    int[] tmp = Arrays.copyOf(tab, tab.length);
    int secMax = 0;
    Arrays.sort(tmp);
    secMax = tmp[tmp.length - 2];
    System.out.println(secMax);
    List<Integer> positions = new ArrayList<>();
    for (int i = 0; i < tab.length; i  ) {
        if (tab[i] == secMax) {
            positions.add(i);
        }
    }
    System.out.println(positions);