My c++ solution with O(n) time and O(1) space


  • 0
    B
    void nextPermutation(vector<int> &num) {
        if ( num.size() == 0 )
            return;
        for ( int i = num.size()-1; i >= 0; i-- )
        {
            if ( i > 0 && num[i] <= num[i-1] )
                continue;
            if ( i == 0 ) {    
                reverse(num.begin(), num.end());
                break;
            }
            int j;
            for ( j = num.size()-1; j >= 0 && num[i-1] >= num[j]; j--);
            int tmp = num[i-1];
            num[i-1] = num[j];
            num[j] = tmp;
            reverse(num.begin()+i, num.end());
            break;
        }
    }

Log in to reply
 

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