博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
遍历数组寻找符合条件的数:力扣(414、628)
阅读量:691 次
发布时间:2019-03-17

本文共 2020 字,大约阅读时间需要 6 分钟。

一、母题

1.

在这里插入图片描述

延伸:既然可以求第三大的数,就可以求第n大或第n小的数。(原则上,n ∈ [ 1 , 3 ] \in[1, 3] [1,3])。

如果n > 3, 那么采用TreeSet来解题。以第4大的数为例子:

TreeSet
ts = 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个最小的数。(允许重复)

  • AC代码
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/

你可能感兴趣的文章