/*
 * Find Second Largest is a real technical interview question.
 * Chances are you will be asked to find the second largest value
 * inside of an array of numbers. You must also be able to filter
 * out duplicate values.  It's important to know how to do this with
 * clean code that is also easy to explain.
 *
 * Resources:
 * https://mdn.org.cn/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
 */

const secondLargestElement = (array) => {
  const largestElement = Math.max(...array)
  let element = -Number.MAX_VALUE

  for (let i = 0; i < array.length; i++) {
    if (element < array[i] && array[i] !== largestElement) {
      element = array[i]
    }
  }

  return element
}

export { secondLargestElement }

问题陈述

给定一个无序数组，编写一个函数来查找数组中的第二大元素。

方法

• 通过循环遍历数组，找到数组中最大的元素，并将该值存储在一个变量中（例如：a）
• 分配一个变量来存储负无穷值，该值存储最小值（例如：b）
• 从 0 到数组大小运行循环。
• 现在检查当前元素是否大于变量“b”并且也不等于变量“a”，该变量是数组中的最大数。
• 如果上述条件为真，则变量 b 存储当前元素。

时间复杂度

• 最佳情况：O(n)
• 平均情况：O(n)
• 最坏情况：O(n)

空间复杂度

最坏情况：O(1)

示例

arr =    [2, 5,  3,  9,  12, 34, 25]
Indexes:  0   1   2   3   4   5   6
a = max(arr) 
(a = 34)
b = float("-inf")

Traverse elements from i = 0 to i = 6
i = 0
Check if b < arr[i] (arr[0]) and arr[0] != a
True : b = arr[0] (b = 2)

i = 1
Check if b < arr[i] (arr[1]) and arr[1] != a
True : b = arr[0] (b = 5)

i = 2
Check if b < arr[i] (arr[2]) and arr[2] != a
False : As b = 5 is greater than the current element arr[2] = 3
continues with the loop

i = 3
Check if b < arr[i] (arr[3]) and arr[3] != a
True : b = arr[3] (b = 9)

i = 4
Check if b < arr[i] (arr[4]) and arr[4] != a
True : b = arr[4] (b = 12)

i = 5
Check if b < arr[i] (arr[5]) and arr[5] != a
False:  As current element is equal to the variable "a" which stores the highest value in the array
continues with the loop

i = 6
Check if b < arr[i] (arr[6]) and arr[6] != a
True : b = arr[6] (b = 25)

Now we get the value 25 in the variable "b", which is the second highest value in the array.

视频说明

解释两种方法的视频