414. Third Maximum Number(第三大的数)

题目：414. Third Maximum Number
描述：Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

来源：力扣（LeetCode）

分析：题目大意就是给你一个不为空的数组（并非有序或无序），让你找出数组中第三大的元素值，如果找不到就返回其最大值，题意就是这么easy！！！

要求：时间复杂度为O（n）！！！！;

解法一：思路就是排序，去重，找值，可以使用ArrayList函数去重，这里我直接用的库里的Array.sort进行排序，排序去重之后的数组中，如果长度大于等于3，返回倒数第三个元素，否则返回倒数第一个元素，即为所求！这个思路比较直接，也容易实现，但其实并不符合题目最后一点的时间复杂度要求，因为只要动用了排序，时间复杂度不会是O(n),可以作为参考解法。

  public static int ArrayList_thrid_Max(int[] arr) {
   
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
   
            if (!list.contains(arr[i])) {
   
                list.add(arr[i]);
            }
        }
        if (list.size() < 3) {
   
            return list.get(list.size() - 1);
        }
        return list.get(list.size() - 3);
    }

**解法二：**直接查找出第一大，第二大，第三大的元素，按需返回即可。时间复杂度O（n）

class Solution {
   
   public static long MIN = Long.MIN_VALUE;
   // public static long MIN = Long.MIN_VALUE;
    public static int thirdMax(int[] arr){
   
        int len = arr.length;
        int max_1 = arr[0];
        long max_2 = MIN;
        long max_3 = MIN;
        for (int i = 1; i <len ; i++) {
   
            int temp = arr[i];
            //如果存在直接跳过，否则进行逐一判断
            if (temp == max_1 || temp == max_2 || temp == max_3)
                continue;
                //搞定最大值
            if (temp>max_1){
   
                max_3 = max_2;
                max_2 = max_1;
                max_1 = temp;
                //搞定第二大的值
            } else if (temp>max_2){
   
                max_3 = max_2;
                max_2 = temp;
                //搞定第三大的值
            }else if (temp>max_3){
   
                max_3  = temp;
            }
        }
        //如果存在第三大值，返回，否则返回最大值
        if (max_3==MIN) return (int) max_1;
        return (int) max_3;
    }
}

当然，还有很多其他优秀的解法和思路，博主小白，更多参考解法待研究ing…