leetcode-414-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:

1
2
3
4
5
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

1
2
3
4
5
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

1
2
3
4
5
6
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.

分析

求数组中第三大的数，没有必要用堆，直接一次遍历然后比较即可。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int thirdMax(int[] nums) {
        Integer max = null;
        Integer max2 = null;
        Integer max3 = null;
        
        for (Integer n: nums) {
            if (n.equals(max) || n.equals(max2) || n.equals(max3)) {
                continue;
            }
            if (max == null || n > max) {
                max3 = max2;
                max2 = max;
                max = n;
            } else if (max2 == null || n > max2) {
                max3 = max2;
                max2 = n;
            } else if (max3 == null || n > max3) {
                max3 = n;
            }
        }
        return max3 == null ? max: max3;
    }
}

相关问题

(M) Kth Largest Element in an Array

题目来源