问题：
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: 1Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]Output: 2Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]Output: 1Explanation: Note that the third maximum here means the third maximum distinct number.Both numbers with value 2 are both considered as second maximum.
解决：
①将数组排序，使用一个计数器，从数组尾部开始，找到第三大的值，即count=3的时候返回即可。耗时8ms.
public class Solution {
public int thirdMax(int[] nums) { Arrays.sort(nums); if (nums.length < 3) { return nums[nums.length -1]; } int count = 1; int thirdMax = nums[nums.length -1]; for (int i = nums.length - 1;i >= 0 ;i --) { if (nums[i] < thirdMax) { thirdMax = nums[i]; count ++; } if(count == 3){ break; } } if(count == 3){ return thirdMax; }else{ return nums[nums.length -1]; } } }②使用三个指针，分别指向第一大，第二大，第三大的值即可。
public class Solution {
public int thirdMax(int[] nums) { long first = Long.MIN_VALUE;//不能使用Integer类型，[1,2,-2147483648]时不通过 long second = Long.MIN_VALUE; long third = Long.MIN_VALUE; for (int i = 0;i < nums.length ;i ++ ) { if (nums[i] > first) { third = second; second = first; first = nums[i]; }else if (nums[i] > second && nums[i] < first) { third = second; second = nums[i]; }else if(nums[i] > third && nums[i] <second){ third = nums[i]; } } return (int)((third == Long.MIN_VALUE || third == second) ? first : third); } }public class Solution {
public int thirdMax(int[] nums) { long first = Long.MIN_VALUE; long second = Long.MIN_VALUE; long third = Long.MIN_VALUE; for (int n : nums) {//采用这种循环方式会更快一些 if( n > first){ third = second; second = first; first = n; } else if( n > second && n < first) { third = second; second = n; } else if( n > third && n < second) { third = n; } } return (int)( (third == Long.MIN_VALUE || third == second) ? first : third); } }