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:

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 {
// Time complexity: O(nlog(N)), n is the size of input array, N is the size of // numbers we want to track.
    public final int N = 3;
    public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            // Don't forget checking duplicates.
            if (set.contains(num)) continue;
            if (set.size() < N || num > set.first()) {
                if (set.size() == N) {
                    set.remove(set.first());
                }
                set.add(num);
            }
        }
        return set.size() == 3 ? set.first() : set.last();
    }
    /**
    public int thirdMax(int[] nums) {
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        int count = 0;
        
        for (int num : nums) {
            // Removed num == max3
            if (num == max1 && count > 0 || 
                num == max2 && count > 1 ||
                num == max3 && count > 2) continue;
            count++;
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            // Added num >= max3
            } else if (num > max3) {
                max3 = num;
            }
        }
        
        if (count >= 3) return max3;
        else return max1;
    }
    */
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s