2021.10.06 - 113.第三大的数

• 1. 题目
• 2. 思路
• • (1) 模拟法
  • (2) TreeSet
• 3. 代码

• 遍历数组，维护三个变量，分别存储最大值、第二大值、第三大值即可。
• 注意！由于数组元素的取值范围是int，因此初始化时变量类型设置为long，初始值设置为Long.MIN_VALUE。

• 遍历数组，利用有序集合TreeSet存储最大值、第二大值、第三大值即可。
• 由于TreeSet的长度为3，因此排序的时间复杂度可以看作O(1)。

import java.util.Set;
import java.util.TreeSet;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int thirdMax(int[] nums) {
        long max1 = Long.MIN_VALUE;
        long max2 = Long.MIN_VALUE;
        long max3 = Long.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max1) {
                max3 = max2;
                max2 = max1;
                max1 = nums[i];
            } else if (nums[i] < max1 && nums[i] > max2) {
                max3 = max2;
                max2 = nums[i];
            } else if (nums[i] < max2 && nums[i] > max3) {
                max3 = nums[i];
            }
        }
        if (max3 == Long.MIN_VALUE) {
            return (int) max1;
        }
        return (int) max3;
    }
}

class Solution1 {
    public int thirdMax(int[] nums) {
        TreeSet set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
            if (set.size() > 3) {
                set.remove(set.first());
            }
        }
        if (set.size() < 3) {
            return set.last();
        }
        return set.first();
    }
}