問題：
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.
大意：
給出一個非空整型數(shù)組，返回數(shù)組中第三大的數(shù)。如果不存在，就返回最大的數(shù)。時間復(fù)雜度必須為O（n）。
例1：輸入：[3, 2, 1]
輸出：1
解釋：第三大的數(shù)為1。例2：
輸入：[1, 2]
輸出：2
解釋：不存在第三大的數(shù)，所以要用最大的數(shù) 2 來代替。例3：
輸入：[2, 2, 3, 1]
輸出：1
解釋：注意這里第三大的數(shù)是指區(qū)分的數(shù)字。兩個 2 都被視為第二大的數(shù)。
思路：
題目要求時間復(fù)雜度為O（n），所以排除使用先排序的方法來做，排序后基本時間復(fù)雜度就超了。
所以只能遍歷一遍來記錄第三大的數(shù)，我們用三個整型變量來記錄，由于題目沒說有沒有負(fù)數(shù)，所以我們沒法定義一個絕對小于數(shù)組中所有數(shù)字的初始值，只能以數(shù)組中第一個數(shù)字來作為初始值，然后遍歷一個一個數(shù)字去比較看應(yīng)該替代三個數(shù)字中哪個數(shù)字，注意如果比第一個數(shù)字大，那么原本第一個數(shù)字的值要移動到第二個，原本第二個數(shù)字的值要移動到第三個，如果替代的是第二個數(shù)字，同樣要把原本第二個數(shù)字的值移動到第三個，道理很簡單。由于我們是用第一個數(shù)字作為初始值的，因此在替換數(shù)字時還有一個原因就是如果第二個和第三個數(shù)字還是初始值，而出現(xiàn)了與初始值不同的數(shù)字，那就不要求比原數(shù)字大了，直接替換并后移，否則如果第一個數(shù)字最大，那即使有第三大數(shù)字也不會記錄下來。
由于題目說了是非空數(shù)組，所以不用考慮空數(shù)組特殊情況。
最后要判斷三個數(shù)字是不是不一樣，不一樣才返回第三大數(shù)字，否則就要返回最大的數(shù)字。
代碼（Java）：
public class Solution {
public int thirdMax(int[] nums) {
int first = nums[0];
int second = nums[0];
int third = nums[0];
for (int i = 0; i < nums.length; i++) {
if (nums[i] > first) {
third = second;
second = first;
first = nums[i];
} else if (nums[i] != first && (nums[i] > second || second == first)) {
third = second;
second = nums[i];
} else if ((nums[i] != first && nums[i] != second) && (nums[i] > third || third == second || third == first)) {
third = nums[i];
}
}
if (first > second && second > third) return third;
else return first;
}
}
合集：https://github.com/Cloudox/LeetCode-Record
