Программа Javascript для третьего по величине элемента в массиве отдельных элементов

Дан массив из n целых чисел, найти третий по величине элемент. Все элементы массива являются различными целыми числами.
Пример :

Input: arr[] = {1, 14, 2, 16, 10, 20}
Output: The third Largest element is 14

Explanation: Largest element is 20, second largest element is 16 
and third largest element is 14

Input: arr[] = {19, -10, 20, 14, 2, 16, 10}
Output: The third Largest element is 16

Explanation: Largest element is 20, second largest element is 19 
and third largest element is 16

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

• Алгоритм:
  1. Сначала перебираем массив и находим максимум.
  2. Сохраните это как первый максимум вместе с его индексом.
  3. Теперь пройдитесь по всему массиву, найдя второй максимум, исключая максимальный элемент.
  4. Наконец, пройдитесь по массиву в третий раз и найдите третий по величине элемент, т.е. исключая максимум и второй максимум.
     

• Выход:
  

The third Largest element is 13

• Анализ сложности:
  • Временная сложность: O(n).
    Поскольку массив повторяется трижды и выполняется за постоянное время
  • Пространственная сложность: O(1).
    Дополнительное пространство не требуется, так как индексы могут храниться в постоянном пространстве.

Эффективный подход : проблема связана с поиском третьего по величине элемента в массиве за один проход. Задачу можно решить, воспользовавшись помощью аналогичной задачи — нахождения второго максимального элемента. Итак, идея состоит в том, чтобы пройти массив от начала до конца и отследить три самых больших элемента до этого индекса (хранящихся в переменных) . Таким образом, после обхода всего массива в переменных будут храниться индексы (или значения) трех самых больших элементов массива.

• Алгоритм:
  1. Создайте три переменные, first , second , Third , для хранения индексов трех самых больших элементов массива. (Изначально все они инициализируются минимальным значением).
  2. Двигайтесь по входному массиву от начала до конца.
  3. Для каждого индекса проверьте, больше ли элемент, чем первый , или нет. Обновите значение first , если элемент больше, и присвойте значение first второму , а второму третьему . Таким образом, самый большой элемент обновляется, и элементы, ранее сохраненные как самые большие, становятся вторыми по величине, а второй по величине элемент становится третьим по величине.
  4. В противном случае, если элемент больше второго , обновите значение второго , и второй по величине элемент станет третьим по величине.
  5. Если предыдущие два условия не выполняются, но элемент больше третьего , то обновите третий .
  6. Вывести значение третьего после обхода массива от начала до конца
     

• Выход:
  

The third Largest element is 13

• Анализ сложности:
  • Временная сложность: O(n).
    Поскольку массив повторяется один раз и выполняется за постоянное время
  • Пространственная сложность: O(1).
    Дополнительное пространство не требуется, так как индексы могут храниться в постоянном пространстве.

Пожалуйста, обратитесь к полной статье о третьем по величине элементе в массиве отдельных элементов для получения более подробной информации!