O(n) time O(1) space.


  • 0
    F

    Use three flags to mark if corresponding value is valid or not, instead of using INT_MIN.

    class Solution {
    public:
        int thirdMax(vector<int>& nums) {
            int first, second, third;
            bool first_valid = false , second_valid = false, third_valid = false;
            for (int i = 0; i < nums.size(); i++) {
                if (!first_valid || nums[i] > first) {
                    third = second;
                    second = first;
                    first = nums[i];
                    if (first_valid) {
                        second_valid = true;
                    }
                    first_valid = true;
                } else if (nums[i] == first) {
                    continue;
                } else if (!second_valid || nums[i]  > second) {
                    third = second;
                    second = nums[i];
                    if (second_valid) {
                        third_valid = true;
                    }
                    second_valid = true;
                } else if (nums[i] == second) {
                    continue;
                }else if (!third_valid || nums[i] > third) {
                    third = nums[i];
                    third_valid = true;
                }
            }
            
            return third_valid ? third : first;
           
        }
    };
    

Log in to reply
 

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