题目链接

题目描述

image.png
image.png

思路一

排序：将数组从大到小排序后，从头开始遍历数组，通过判断相邻元素是否不同，来统计不同元素的个数。如果能找到三个不同的元素，就返回第三大的元素，否则返回最大的元素。
后面加个去重也可以

  1. // 排序
  2. public int thirdMax(int[] nums) {
  3.     Arrays.sort(nums);
  4.     reverse(nums);
  5.     for (int i = 1, diff = 1; i < nums.length; i++) {
  6.         if (nums[i] != nums[i - 1] && ++ diff == 3) {
  7.             return nums[i];
  8.         }
  9.     }
  10.     return nums[0];
  11. }
  13. private void reverse(int[] nums) {
  14.     int left = 0;
  15.     int right = nums.length - 1;
  17.     while (left < right) {
  18.         nums[left] ^= nums[right];
  19.         nums[right] ^= nums[left];
  20.         nums[left] ^= nums[right];
  21.         left++;
  22.         right--;
  23.     }
  24. }

思路二

image.png
可以使用 treeSet 的特性

  1. public int thirdMax(int[] nums) {
  2.     TreeSet<Integer> s = new TreeSet<Integer>();
  3.     for (int num : nums) {
  4.         s.add(num);
  5.         if (s.size() > 3) {
  6.             s.remove(s.first());
  7.         }
  8.     }
  9.     return s.size() == 3 ? s.first() : s.last();
  10. }