Нужно найти два максимальных элемента массива за одно прохождение О(n), и учесть нюанс, когда первый элемент может быть максимальным.
Вот мои идеи
Как решить задачу?
Вариант с предварительной сортировкой неверный. Там больше сложности чем требуется по условию.
Второй вариант больше похож на правду. Я бы результат (два максимальных числа) хранил в сортированном массиве и наполнял/обновлял его в один проход по оригинальному массиву.
К стати на одном собеседовании мне задали задачу просто найти 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 одинаковых числа будут ответом)
- отсортирован ли исходный массив
- оптимизировать решение под память или под скорость выполнения
- однороден ли исходный массив
сказано, что массив чисел. Что такое однородность?
скорее всего нет, иначе вопроса не было бы на собеседовании
Однородность типов. “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 - это по-ленивому. Можно хранить в двух переменных, так эффективнее по памяти