414. Third Maximum Number

发表于 | 更新于: | 分类于 | 本文总阅读量 次
| 字数统计: 1,195 | 阅读时长 ≈ 7
  • 27.9%

https://leetcode.com/problems/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).

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

Output: 1

Explanation: The third maximum is 1.
1
2
3
4
5
6
7
Example 2:
Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, 
so the maximum (2) is returned instead.
1
2
3
4
5
6
7
8
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.

https://discuss.leetcode.com/topic/63903/short-easy-c-using-set

方法一：

Short easy C++ using set

Track the largest three values in a set.

1
2
3
4
5
6
7
8
9
int thirdMax(vector<int>& nums) {
    set<int> top3;
    for (int num : nums) {
        top3.insert(num);
        if (top3.size() > 3)
            top3.erase(top3.begin());
    }
    return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
}

我的代码实现：

主要几点，set是有序的，set可以去重。erase函数用法，对于地址的解析。begin, rbegin函数。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> set;
        for(auto num:nums){
            set.insert(num);
            if(set.size()>3)
                set.erase(set.begin());
        }
        return set.size()==3?*set.begin() : *set.rbegin();
    }
};

Alternatively (not sure which one I like better):

1
2
3
4
5
6
7
int thirdMax(vector<int>& nums) {
    set<int> top3;
    for (int num : nums)
        if (top3.insert(num).second && top3.size() > 3)
            top3.erase(top3.begin());
    return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
}

python

https://discuss.leetcode.com/topic/64696/a-python-amusing-solution-which-actually-beats-98

A python amusing solution, which actually beats 98%…

1
2
3
4
5
6
7
def thirdMax(self, nums):
        nums = set(nums)
        if len(nums) < 3:
            return max(nums)
        nums.remove(max(nums))
        nums.remove(max(nums))
        return max(nums)

https://discuss.leetcode.com/topic/70613/intuitive-and-short-python-solution

Intuitive and Short Python solution

Time complexity is O(n), space complexity is O(1).

1
2
3
4
5
6
7
8
9
class Solution(object):
    def thirdMax(self, nums):
        v = [float('-inf'), float('-inf'), float('-inf')]
        for num in nums:
            if num not in v:
                if num > v[0]:   v = [num, v[0], v[1]]
                elif num > v[1]: v = [v[0], num, v[1]]
                elif num > v[2]: v = [v[0], v[1], num]
        return max(nums) if float('-inf') in v else v[2]

https://discuss.leetcode.com/topic/63962/python-2-5-lines-o-n-time-o-1-space

Python: 2-5 lines, O(n) time, O(1) space

1
2
3
4
5
6
def thirdMax(self, nums):
    l = [float('-inf')] * 3
    for n in nums:
        if n > l[0] and n not in l:
            heapq.heappushpop(l, n)
    return l[0] if l[0] != float('-inf') else max(l)

A slightly shorter but uglier version based on the same concept is:

Although I’m not sure whether the second version is still O(1) space. Does anyone know whether the Python interpreter will create the whole list comprehension in memory even though it is not being assigned anywhere?

Update: two line solution by @StefanPochmann below.

1
2
3
4
def thirdMax(self, nums):
    l = [float('-inf')] * 3
    [heapq.heappushpop(l, n) for n in nums if n > l[0] and n not in l]
    return l[0] if l[0] != float('-inf') else max(l)

java

https://discuss.leetcode.com/topic/63086/java-priorityqueue-o-n-o-1

Java PriorityQueue O(n) + O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int thirdMax(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (!set.contains(i)) {
                pq.offer(i);
                set.add(i);
                if (pq.size() > 3) {
                    set.remove(pq.poll());
                }
            }
        }
        if (pq.size() < 3) {
            while (pq.size() > 1) {
                pq.poll();
            }
        }
        return pq.peek();
    }
}

Nice solution, and here is the concise version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int thirdMax(int[] nums) {
       PriorityQueue<Integer> pq = new PriorityQueue<>();
       Set<Integer> set = new HashSet<>();
       for(int n : nums) {
           if(set.add(n)) {
               pq.offer(n);
               if(pq.size() > 3 ) pq.poll();
           }
       }
       if(pq.size() == 2) pq.poll();
       return pq.peek();
    }
}

https://discuss.leetcode.com/topic/62236/java-solution-in-0ms-run-time-o-n-and-space-o-1

Java solution in 0ms run time O(n) and space O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int thirdMax(int[] nums) {
        int max, mid, small, count;
        max = mid = small = Integer.MIN_VALUE;
        count = 0;  //Count how many top elements have been found.

        for( int x: nums) {
            //Skip loop if max or mid elements are duplicate. The purpose is for avoiding right shift.
            if( x == max || x == mid ) {
                continue;
            }

            if (x > max) {
                //right shift
                small = mid;
                mid = max;

                max = x;
                count++;
            } else if( x > mid) {
                //right shift
                small = mid;

                mid = x;
                count++;
            } else if ( x >= small) { //if small duplicated, that's find, there's no shift and need to increase count.
                small = x;
                count++;
            }
        }

        //"count" is used for checking whether found top 3 maximum elements.
        if( count >= 3) { 
            return small;
        } else {
            return max;
        }
    }

https://discuss.leetcode.com/topic/63671/o-n-time-o-1-space-java-short-solution

O(n) time O(1) space Java short solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 i:nums){
            if(i>first){
                third=second;
                second=first;
                first=i;
            }else if(i==first)
                continue;
            else if(i>second){
                third=second;
                second=i;
            }else if(i==second)
                continue;
            else if(i>third){
                third=i;
            }
        }
        return third==Long.MIN_VALUE?(int)first:(int)third;
    }
}

https://discuss.leetcode.com/topic/65119/java-solution-using-treeset

Java Solution Using TreeSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public final int N = 3;
    public int thirdMax(int[] nums) {
        if (nums.length == 0) return 0;

        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) continue;
            if (set.size() < N || nums[i] > set.first()) {
                if (set.size() == N) set.remove(set.first());
                set.add(nums[i]);
            }
        }
        return set.size() == N ? set.first() : set.last();
    }
}
谢谢你，可爱的朋友。