遍历数组寻找符合条件的数：力扣（414、628）

忘是亡心i 2023-01-13 09:37 182阅读 0赞

# 一、母题 #

1.[414. 第三大的数][414.]  
![在这里插入图片描述][20210417143926541.png]

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

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

TreeSet<Integer> 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.[628. 三个数的最大乘积][628.]  
分类讨论的思想，分析：  
①均为正数：找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);
        }
    }

[414.]: https://leetcode-cn.com/problems/third-maximum-number/
[20210417143926541.png]: /images/20221022/c1deeab09ec94c1bb35b253f4e3be685.png
[628.]: https://leetcode-cn.com/problems/maximum-product-of-three-numbers/