Недавно я решал проблему, в которой одна из подзадач, которую нужно было решить, заключалась в нахождении второго по величине числа в массиве целых чисел. Я достаточно скромен, чтобы признать это: я немного замерз. Я знаю типичные методы перемещения / возврата в начале и в конце, которые мы используем постоянно (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;
}

Не обязательно лучше, учитывая большее использование памяти и аналогичную временную сложность, но полезно знать несколько способов решения этой проблемы.

И запомни…

Упорство ›талант.