My short c++ code, o(n) time, o(1) space


  • 1
    D

    Find the rightmost sub-sequence that is in the reverse order, then reverse it, and at last swap the one just before such sub-sequence, nums[i], with the first element in that sub-sequence that is larger than nums[i]. Finding the index j can be done by binary search.

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
           int len = nums.size();
           int i, j;
           if(len>1)
           {
               i= len-2;
               while(i>=0 && nums[i]>=nums[i+1]) i--; // find the rightmost reverse sub-sequence
               reverse(nums.begin()+i+1, nums.end()); // reverse it 
               if(i>=0)
               {
                   for(j=i+1;j<len && nums[j]<=nums[i]; j++); // find the first one that is larger than nums[i]
                   swap(nums[j], nums[i]); // swap
               }
           }
        }
    };

Log in to reply
 

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