Java Solution in O(n) run time and O(1) space.


  • 0
    S
        public int thirdMax(int[] nums) {
            Integer[] top3 = new Integer[3]; // initialized array contains nulls
            for (int i : nums) trySet(top3, i);
            return top3[2] != null ? top3[2] : top3[0];
        }
    
    /** Try add n to the top array.
    * Array will be filled from max to min values.
    * For instance: input = [2,2,3,1,4], top = [4,3,2]. 
    */
        void trySet(Integer[] top, int n) {
            int current = n;
            for (int i=0; i<top.length; i++) {
                //this place is empty in top array, so set the current and break.
                if (top[i] == null) {
                    top[i] = current;
                  break;
                }
               // we found the duplicate value, so we can stop.
                if (current == top[i]) {
                    break;
                }
                // if current > top[i] we should updated the top[i],
                // and then compare top[i] with top[i+1] and so on.
                if (current > top[i]) {
                    int temp = top[i];
                    top[i] = current;
                    current = temp;
                }
            }
        }
    

Log in to reply
 

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