4ms C++ solution, does MAX_INTEGER * n consider as O(n) ?


  • -1
    B

    Does this consider as an O(n) solution? It will at most run MAX_INTEGER * nums.size() times, and usually it does not since we stop when we find that number. But if

    1. all numbers in the array are positive numbers (say n numbers)

    2. the missing positive integer is max(all numbers in the array) + 1 (denote by K)

    then the time complexity is K * n, but it can also be wrote as sum_{1}^{n+1}, there is a n square in it...

    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int missing = 1;
            while(true) {
                bool find = false;
                for(int i = 0; i < nums.size(); i++) {
                    if (nums[i] - missing == 0) { // find that positive integer
                        missing ++;
                        find = true;
                        break;
                    }
                }
                if (!find) return missing;
            }
    
        }
    };

  • 0
    P

    This is O(n^2).

    Consider the input n, n-1, n-2, ..., 1


  • 0
    B

    Yes I see, thanks.


Log in to reply
 

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