问题描述
给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。
示例 1:
输入:[3, 2, 1]
输出:1
解释:第三大的数是 1 。
示例 2:
输入:[1, 2]
输出:2
解释:第三大的数不存在, 所以返回最大的数 2 。
示例 3:
输入:[2, 2, 3, 1]
输出:1
解释:注意,要求返回第三大的数,是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数,它们都排第二。在所有不同数字中排第三大的数为 1 。
力扣原题目地址:https://leetcode.cn/problems/...
解决方案
方案一 去重并排序以后,再看是否存在第三大的数
var thirdMax = function (nums) {
let n = [...new Set(nums)].sort(function (a, b) { // 1. 使用Set去重,并从大到小排列
return b - a
})
if (n.length >= 3) { // 2. 操作完以后,如果还有3或多项,就直接取第三大的数返回即可
return n[2]
} else { // 3. 操作完以后,有可能只剩一个或者两个了,按照题意,那就直接返回最大的即可
return n[0]
}
};
方案二 定义三个-Infinity
循环比较赋值
在看下方代码之前,我们要回顾两个知识
知识复习一:交换两个变量的值
最常见的就是定义一个临时变量temp作为交换的中转站,比如下方我们要交换a和b的值
var a = 666;
var b = 777;
/* 定义临时变量temp中转站 */
var temp = null;
temp = a
a = b
b = temp
当然,更好的方法是不定义变量,利用数组的解构特性
去做交换对应,比如:
let a = 666;
let b = 777;
[a, b] = [b, a]
console.log(a, b); // 777 666
为什么要提到这个呢?
因为下方代码循环中,需要比较最大、第二大、第三大的值。如果新值(循环中的项),比最大的还大,那么就把这个新值交换为最大,原来的最大,交换为第二大,原来的第二大,交换为第三大;
按此规律循环比较值大小,去做值交换即可
知识复习二:Infinity无穷大,与-Infinity无穷小
Infinity
这个平常貌似用的不多。用的话,也就在css动画中,让动画无限运行下去,比如:animation: rotation 3s linear infinite;
但是刷算法题要用到啊(手动狗头)
之所以提到这个Infinity
是因为在初始状态下,我们需要定义三个变量:最大
、第二大
、第三大
的3个变量,后续的循环中,每一项肯定是要交换值,比较的,所以只能用-Infinity
,定义3个初始变量。
与之对应的最大数、最小数也可以使用Number.MAX_VALUE
和-Number.MAX_VALUE
去表示。另外有一篇译文写的挺好,分享一下:https://blog.fundebug.com/201...
复习了这两个知识点,接下来再看代码,就很好理解了
代码
var thirdMax = function (nums) {
let biggest = -Infinity // 1. 定义最大数初始值为无穷小
let secondLargest = -Infinity // 2. 定义第二大数初始值为无穷小
let thirdLargest = -Infinity // 3. 定义第三大数初始值为无穷小
for (let i = 0; i < nums.length; i++) { // 4. 遍历数组去比较大小
if (nums[i] > biggest) { // 5. 如果新的数比最大值还要大,那么新的数当老大,原来的老大退居成老二了,原来的老二退居成老三了,原来的老三直接`退休了`
[biggest, secondLargest, thirdLargest] = [nums[i], biggest, secondLargest]
} else if (nums[i] == biggest) { // 6. 如果新的数和老大一样,那么就不交换了,因为相当于没变,就直接忽略之continue跳过,当然不加continue也是没问题的,加上效率高一些
continue
} else if (nums[i] > secondLargest) { // 7. 如果新的数比老二大,但是没有老大大,那么老大不用变、新的数当老二、原来的老二就被降级成老三了。原来的老三依旧直接退休了
[biggest, secondLargest, thirdLargest] = [biggest, nums[i], secondLargest]
} else if (nums[i] == secondLargest) { // 8. 这个同6. 一样。不赘述
continue
} else if (nums[i] > thirdLargest) { // 9. 如果新来的数,只比老三大一些,那么,老大、老二不用动。新来的数直接把原来的老三赶走,自己当老三就行喽
[biggest, secondLargest, thirdLargest] = [biggest, secondLargest, nums[i]]
}
}
// 10. 最后要判断一下,因为有可能找不到老三(比如数组只有两项,或者数组有很多项,但是都重复了,毕竟重复的会被忽略)
if (thirdLargest === -Infinity) { // 11. 若老三还是初始状态,就说明没有老三(老三的位子空缺)
return biggest // 12. 依照题意,返回老大
} else {
return thirdLargest // 13. 老三的位子有人做,那就返回老三
}
};
由上述复习知识点,可得到Infinity
也可以使用Number.MAX_VALUE
替代使用,所以上述代码,可以换成:
var thirdMax = function (nums) {
let biggest = -Number.MAX_VALUE
let secondLargest = -Number.MAX_VALUE
let thirdLargest = -Number.MAX_VALUE
for (let i = 0; i < nums.length; i++) {
if (nums[i] > biggest) {
[biggest, secondLargest, thirdLargest] = [nums[i], biggest, secondLargest]
} else if (nums[i] == biggest) {
continue
} else if (nums[i] > secondLargest) {
[biggest, secondLargest, thirdLargest] = [biggest, nums[i], secondLargest]
} else if (nums[i] == secondLargest) {
continue
} else if (nums[i] > thirdLargest) {
[biggest, secondLargest, thirdLargest] = [biggest, secondLargest, nums[i]]
}
}
if (thirdLargest === -Number.MAX_VALUE) {
return biggest
} else {
return thirdLargest
}
};
总结
好了,大眼一瞅,发现的确是方案二的时间复杂度好一些,当然定义了三个变量,所以空间复杂度多一点,不过,整体思想还是空间换时间呗^_^