leetcode third maximum number

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).

The following solutions are all stealed from A short easy cpp solution using set:

cpp version:

class Solution {
    public:
    int thirdMax(vector<int>& nums) {
        set<int> top3;
        for (auto num : nums) {
            top3.insert(num);
            if (top3.size() > 3)
                top3.erase(top3.begin());
        }
     return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
    }
};

the same idea in java:

public class Solution {
    public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int num : nums) {
            set.add(num);
            if(set.size() > 3) {
                set.remove(set.first());
            }
        }
        return set.size() == 3 ? set.first() : set.last();
    }
}

We can see the cpp and java version above is very similar. A person in the discussion presented a question that std::set usually uses red-black tree, so wouldn’t the solution be nlogn?

The answer to the presented problem is since we only have 3 elements, insert/delete is a constant time operation. Don’t stick to O(nlogn) concept. What’s more, if dive into the problem, we can find the following content about insert operation complexity from cplusplus.com:

If a single element is inserted, logarithmic in size in general, but amortized constant if a hint is given and the position given is the optimal.

Let’s see the same idea using python:

class Solution(object):
    def thirdMax(self, nums):
        l = []
        for n in set(nums):
            bisect.insort(l, -n)
            if len(l)>3:
                l.pop()
        return -l[2] if len(l)>2 else -l[0]

I am not an expert in python , yet, so the python solution is not so clear and understandable at my first glance. Actually, the reason is that I didn’t know bisect.insort().

The idea could also be used to get the top k items in a large array, whereas you need pay more attention to a certain case:

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.

If numbers with the same value can not be considered as the same one, the result is unexpected. I did make a mistake here in the past. In Bayesian Personalized Ranking algorithm, I need to obtain the top k items from a list. At that time I used the similar solution, though the final result seemingly looked normal, it was indeed wrong. ⤧ Next post Switch from spacemacs to vim painlessly