本文共 2020 字,大约阅读时间需要 6 分钟。
1.
延伸:既然可以求第三大的数,就可以求第n大或第n小的数。(原则上,n ∈ [ 1 , 3 ] \in[1, 3] ∈[1,3])。
如果n > 3, 那么采用
TreeSet
来解题。以第4大的数为例子:
TreeSetts = new TreeSet<>();for(int num : nums) { ts.add(num); if(ts.size() > 4) ts.remove(ts.first());}return ts.size() < 4 ? ts.last() : ts.first();
2.通解
class Solution { public int thirdMax(int[] nums) { long max1 = Long.MIN_VALUE, max2 = Long.MIN_VALUE, max3 = Long.MIN_VALUE; for(int num : nums) { if(num == max1 || num == max2 || num == max3) continue; if(num > max1) { max3 = max2; max2 = max1; max1 = num; } else if(num > max2) { max3 = max2; max2 = num; } else if(num > max3) { max3 = num; } } return max3 == Long.MIN_VALUE ? (int)max1 : (int)max3; }}
核心思路:求第n大/小的数,就定义n个变量来存储。
比如:要求第3大的数,那么就用max1,max2,max3分别来存储第1、2、3大的数。 本题的坑点: ①nums[i]最小值可以是Integer.MIN_VALUE,所以max1~max3的类型为long; ②过滤掉重复数;
1.
分类讨论的思想,分析: ①均为正数:找3个最大的数 ②均为负数:找3个最大的数 ③正负数混杂:即可能是3个最大的正数,也可能是1个最大的正数和2个最小的负数。所以,本题的实质是遍历数组寻找3个最大的数和2个最小的数。(允许重复)
class Solution { public int maximumProduct(int[] nums) { int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE; int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE; for(int num : nums) { if(num > max1) { max3 = max2; max2 = max1; max1 = num; } else if(num > max2) { max3 = max2; max2 = num; } else if(num > max3) { max3 = num; } if(num < min1) { min2 = min1; min1 = num; } else if(num < min2) { min2 = num; } } return Math.max(max1 * max2 * max3, min1 * min2 * max1); }}
转载地址:http://lxhhz.baihongyu.com/