Недавно я решал проблему, в которой одна из подзадач, которую нужно было решить, заключалась в нахождении второго по величине числа в массиве целых чисел. Я достаточно скромен, чтобы признать это: я немного замерз. Я знаю типичные методы перемещения / возврата в начале и в конце, которые мы используем постоянно (pop, shift, unshift и т. Д.). Но как насчет второго по последнему слову?
Давайте рассмотрим несколько сценариев с возрастающей сложностью.
Самый простой случай: отсортированный массив
Если вы знаете, что массив уже отсортирован, получить второе по величине число просто:
const arr = [1, 2, 3]; function findSecondLargest(arr) { return arr[arr.length - 2]; }
Это вернет элемент, который находится на позиции длины массива минус 2. Это 2, второе по величине число.
Чуть сложнее: несортированный массив
Что делать, если мы не знаем, отсортирован ли наш массив? Всего один дополнительный шаг: отсортируйте его!
const arr = [1, 3, 2]; function findSecondLargest(arr) { const arrSorted = arr.sort((a, b) => a - b); return arrSorted[arr.length - 2]; }
Это сначала отсортирует ваш массив, а затем применит тот же процесс, что и раньше: вернет элемент, который находится на позиции длины массива, минус 2, также 2.
Самый сложный: беспорядочный массив
Что, если мы не только не можем предположить, что наш массив отсортирован, но и в нем есть дубликаты?
Во-первых, мы предполагаем, что хотим удалить дубликаты, чтобы, если бы массив был const arr = [3, 1, 1, 2, 3, 2], мы все равно хотели бы вернуть 2. Вот алгоритм:
- Создайте новый массив с удаленными дубликатами
- Сортировать.
- Вернуть предпоследний
Вот код:
function findSecondLargest(arr) { const distinct = [...new Set(arr)]; const distinctSorted = distinct.sort((a, b) => a - b); return distinctSorted[distinctSorted.length - 2]; }
Бонус: делать это без сортировки вручную
Если нам интересно, мы могли бы решить задачу, изложенную ранее, с помощью другого метода:
- Создайте новый массив с удаленными дубликатами
- Получите наибольшее число и отфильтруйте это число из массива, удалив дубликаты.
- Вернуть новое наибольшее число
Вот код для этого:
function findSecondLargest(arr) { const distinct = [...new Set(arr)]; const maxNum = Math.max(...distinct); const filteredMaxOut = distinct.filter((num) => num < maxNum); const secondMax = Math.max(...filteredMaxOut); return secondMax; }
Не обязательно лучше, учитывая большее использование памяти и аналогичную временную сложность, но полезно знать несколько способов решения этой проблемы.
И запомни…
Упорство ›талант.