414.md

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.

思路：

   遍历三次数组找出前三个最大值即可。第二次遍历跳过第一次得出的最大值，遍历第三次跳过第一第二大值。
   使用flag标记是否更新了第三大值，如果没更新返回第一大值，否则返回第三大值。
   
   知识点：golang初始化最小值为  max = int(^uint(0)>>1) min = ^max

代码：

func thirdMax(nums []int) int {
    min := ^(int(^uint(0) >> 1))
    top3 := []int{min, min, min}
    for _, value := range nums {
        if value >= top3[0] {
            top3[0] = value
        }
    }
    for _, value := range nums {
        if value != top3[0] && value >= top3[1] {
            top3[1] = value
        } 
    }
    flag := false
    for _, value := range nums {
        if value != top3[0] && value != top3[1] && value >= top3[2] {
            top3[2] = value
            flag = true
        }
    }
    if flag {
        return top3[2]
    } else {
        return top3[0]
    }
    
}