刷题之旅从数组类型的题目开始。第十九道题目是第三大的数，对应leetcode的题号为414。

image

题目描述

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

1
2
3
4
5
输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例 2:

1
2
3
4
5
输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

1
2
3
4
5
输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。

存在两个值为2的数，它们都排第二。

解题思路

思路一：

  1. 维护一个只有3个元素的TreeSet，如果大于三个元素就就把Set中的最小最小值remove掉。
  2. 最后如果Set中元素小于3就返回Set最大值，否则返回最小值。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0) throw new RuntimeException("error");

        TreeSet<Integer> set = new TreeSet<>();
        for (Integer elem : nums) {
            set.add(elem);
            if (set.size() > 3) set.remove(set.first());
        }
        
        return set.size() < 3 ? set.last() : set.first();   // set.last() 里面最大的元素
    }
}

思路二：

  1. 用三个变量来存放第一大，第二大，第三大的元素的变量，分别为one, two, three，初始化为Integer.MIN_VALUE；
  2. 遍历数组，若该元素比one大则往后顺移一个元素，比two大则往往后顺移一个元素，比three大则赋值个three；
  3. 最后得到第三大的元素，若没有则返回第一大的元素。

其中需要一个细节，就是如下示例:

1
[1,1,2]输出2

这个可以理解，因为有效的只有1和2，那么按照题意没有第三大的数字就返回最大的元素即可。不过当出现下面：

1
[1,2,-2147483648]输出-2147483648

也可以理解，因为-2147483648确实就是第三大数字，不过这个数字比较特殊，是java的整型类型最小的数字，即Integer.MIN_VALUE，那么如果不对这个数字做个处理，而是简单粗暴地判断第三大元素是Integer.MIN_VALUE就会出错。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int thirdMax(int[] nums){
        //只有一个元素的时候，没有第三大的数字，直接返回唯一的元素即可
        if(nums.length == 1){
            return nums[0];
        }
        //只有两个数组的时候，也没有第三大的数字，直接返回最大值即可
        if(nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }
        //第一大数字
        int firstMax = Integer.MIN_VALUE;
        //第二大数字
        int secondMax = Integer.MIN_VALUE;
        //第三大数字
        int thirdMax = Integer.MIN_VALUE; 
        //计数，看实际不一样的数字有几个
        int count = 0;
        //其中需要注意数组是否出现过Integer.MIN_VALUE，出现过就count++下，只要加一次
        boolean minflag = true;
        for(int i=0;i<nums.length;i++){
            if(nums[i] == Integer.MIN_VALUE && minflag){
                count++;
                minflag = false;
            }
            if(nums[i] > firstMax){
                count++;
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = nums[i];
            }else if(nums[i] != firstMax && nums[i] > secondMax){
                count++;
                thirdMax = secondMax;
                secondMax = nums[i];
            }else if(nums[i] != firstMax && nums[i] != secondMax && nums[i] > thirdMax){
                count++;
                thirdMax = nums[i];
            }
        }
        //当计数大于3时，说明数组有有效的第三大数字，返回thirdmax即可，否则返回数组的最大值即可
        return count >= 3 ? thirdMax : firstMax;
    }
}