题目
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. 我的解答 public class Solution { public int thirdMax(int[] nums) { ArrayList<Integer> list = new ArrayList<Integer>(); HashSet<Integer> set = new HashSet<>(); int size = 1; list.add(nums[0]); set.add(nums[0]); for(int i = 1; i < nums.length; i ++){ int num = nums[i]; if(!set.contains(num)){ if(num > list.get(size - 1)) list.add(num); else if(size - 2 >= 0 && num > list.get(size - 2)) list.add(size - 1, num); else if(size - 3 >= 0 && num > list.get(size - 3)) list.add(size - 2, num); else list.add(0, num); size ++; set.add(num); } } if(list.size() >= 3) return list.get(size -3); else return list.get(size - 1); } }好的答案
public class Solution { public int thirdMax(int[] nums) { // 前三个最大值初始为null Integer max1 = null; Integer max2 = null; Integer max3 = null; for(Integer num : nums){ // 判断包装类是否包含在前三个最大值中；equal()方法既可以判断有值包装类和包装类，又判断有值包装类和null值 if(num.equals(max1) || num.equals(max2) || num.equals(max3)) continue; // 判断max1是否赋值过，即是否为null；==可以判断对象是否为null，equal()不能判断null是否为null if(max1 == null || num > max1){ max3 = max2; max2 = max1; max1 = num; }else if(max2 == null || num > max2){ max3 = max2; max2 = num; }else if(max3 == null || num > max3){ max3 = num; } } return max3 == null ? max1 : max3; } } 解析：遍历一遍数组，挑选出前三个最大的元素；我使用了集合，好的答案直接使用了变量；相比较而言节省了集合操作耗费的时间。
