C++ O(n) time and O(1) space, VERY EASY understanding


  • 0
    F
    class Solution {
    public:
    
      int thirdMax(vector<int>& nums) {
        // max[i] : the (i+1)th maximum number, i start from zero
        int min, max[3];
        int n = nums.size(); // non-empty means n greater then zero
    
        min = max[0] = nums[0];
        // finds the `first` max number
        for (int i = 0; i < n; i++) {
          if (min > nums[i]) min = nums[i];
    
          if (max[0] < nums[i]) max[0] = nums[i];
        }
        // find the (j+1)th max numbers
        for (int j = 1; j < 3; j++) {
          max[j] = min;
    
          for (int i = 0; i < n; i++) {
            if ((max[j] <= nums[i]) && (nums[i] < max[j - 1])) max[j] = nums[i];
          }
    
        }
    
        if (max[1] == min) return max[0];
        else return max[2];
      }
    };
    

    the first for loop finds the first max number, the second for loop with a nested for loop will find the second and the third max numbers.

    Time complexity: O(k*n) where k is 3 here, therefore O(3*n) is still O(n)


Log in to reply
 

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