Java, two solutions: maintaining three pointers + priority queue


  • 0
    E

    The first approach is to scan the array, saving the top three elements in local variables. Unlike others' solutions, this will work for both int[] and long[] input arrays:

    public class Solution {
        public int thirdMax(int[] nums) {
            Integer first = null, second = null, third = null;
            for (int i : nums) {
                if (first == null || i > first) {
                    third = second == null ? null : second;
                    second = first == null ? null : first;
                    first = i;
                } else if (second == null || (i > second && i != first)) {
                    if (i == first) continue;
                    third = second == null ? null : second;
                    second = i;
                } else if (third == null || (i > third && i != first && i != second)) {
                    if (i == first || i == second) continue;
                    third = i;
                }
            }
            if (second == null || third == null) return first;
            return third;
        }
    

    Another approach is more concise and much easier to code up: while scanning the input array, maintain a minimum oriented priority queue of size three. Since Java's implementation of priority queue allows duplicates, we need an auxiliary set to keep track of the unique elements.
    Implementation:

    public class Solution {
        public int thirdMax(int[] nums) {
            Set<Integer> set = new HashSet<>();
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            for (int i : nums) {
                if (set.add(i)) pq.add(i);
                if (pq.size() > 3) {
                    int min = pq.poll();
                    set.remove(min);
                }
            }
            if (pq.size() == 3) return pq.poll();
            while (pq.size() > 1) pq.poll();
            return pq.poll();
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.