Два максимальных элемента массива

Нужно найти два максимальных элемента массива за одно прохождение О(n), и учесть нюанс, когда первый элемент может быть максимальным.
Вот мои идеи
Как решить задачу?

Вариант с предварительной сортировкой неверный. Там больше сложности чем требуется по условию.

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

1 лайк

К стати на одном собеседовании мне задали задачу просто найти 2 максимальных. Я пытался сделать где-то так, как ты написал, но меня выругали, что я увожу в дебри и дали подсказку, что можно было сначала отсортировать. Хоть вопрос был не по JS, а вообще в подходе к программированию (т.е. даже нет встроенной функции sort).

// variant 3
var twix = [task[0], task[1]];

for (var a = 0; a < task.length; a++) {
  if (task[a] > twix[0]) {
    twix[0] = task[a];
  } else if (task[a] > twix[1]) {
    twix[1] = task[a];
  }
}

alert("variant 3: " + twix[0] + " " + twix[1]);

Так попробовал, но второе число не нашло.
А ты уверен, что у variant 2 O(n) меньше, чем у variant 1 ? Сортировка занимает 1 цикл

Очевидно что не из-за ограниченности идеи а из-за реализации.

В js под капотом quick sort со сложностью O(n log(n)) в среднем.

хотя да, сортировку за 1 цикл не выполнить в большом массиве

Простого ответа “найти 2 наибольших числа” в массиве нет. Поэтому корректно узнать детали прежде чем предлагать решение.

  • что делать если в массиве 1 исходный элемент (ответом считается что 1 максимальный или 2 одинаковых числа будут ответом)
  • отсортирован ли исходный массив
  • оптимизировать решение под память или под скорость выполнения
  • однороден ли исходный массив
1 лайк

сказано, что массив чисел. Что такое однородность?

скорее всего нет, иначе вопроса не было бы на собеседовании

Однородность типов. “999” число (если не про тип, а про суть) и 999 число.

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

Работает

// variant 3
var maxValues = [task[0]];

for (let a = 0; a < task.length; a++) {
  if (task[a] > maxValues[maxValues.length - 1]) {
    maxValues.push(task[a]);
  }
}

alert(
  "variant 3: " +
    maxValues[maxValues.length - 1] +
    " " +
    maxValues[maxValues.length - 2]
);

Вообще, такие вопросы на собеседовании, из какой темы? Вроде бы не классические алгоритмы. Оптимизация кода? Что нужно знать, чтобы быть готовым к такому роду задач?
…Хотя O(n) это алгоритмы.

Это некорректное решение

var task = [1, 3, 2, 3]

// variant 3
var maxValues = [task[0]];

for (let a = 0; a < task.length; a++) {
  if (task[a] > maxValues[maxValues.length - 1]) {
    maxValues.push(task[a]);
  }
}

console.log(
    maxValues[maxValues.length - 1] +
    " " +
    maxValues[maxValues.length - 2]
);

Ожидаю увидеть в результате две тройки, вижу 3, 1.

в if-e > поменять на >=, тогда находит

Все равно не работает для другой последовательности чисел:

var task = [3, 5, 4]

// variant 3
var maxValues = [task[0]];

for (let a = 0; a < task.length; a++) {
  if (task[a] >= maxValues[maxValues.length - 1]) {
    maxValues.push(task[a]);
  }
}

console.log(
    maxValues[maxValues.length - 1] +
    " " +
    maxValues[maxValues.length - 2]
);

Ожидаю 5,4, а вижу 5,3. Тут нужно не “приглаживать” код, а пересмотреть решение.

¯\(ツ)
Пригладил ), решает вышеперечисленные проблемы.

// variant 3
var maxValues = [task[0]];

for (let a = 0; a < task.length; a++) {
  if (task[a] > maxValues[maxValues.length - 1]) {
    maxValues.push(task[a]);
    continue;
  }

  if(task[a] > maxValues[maxValues.length - 2]) {
    maxValues[maxValues.length - 2] = task[a];
  }
}

alert(
  "variant 3: " +
    maxValues[maxValues.length - 1] +
    " " +
    maxValues[maxValues.length - 2]
);

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

Но с push - это по-ленивому. Можно хранить в двух переменных, так эффективнее по памяти

1 лайк