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

  • 1

    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 {
        void nextPermutation(vector<int>& nums) {
           int len = nums.size();
           int i, j;
               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 
                   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.