4 line, 12ms c++ code


  • 4
    A
    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int i;
            for(i = nums.size() - 1;i > 0 && nums[i-1] >= nums[i];i--);
            std::reverse(nums.begin() + i, nums.end());
            if (i>0) swap(nums[i-1],*upper_bound(nums.begin() + i, nums.end(),nums[i-1]));
        }
    };
    

    Thanks for the upper_bound idea from:
    https://leetcode.com/discuss/41925/solution-lines-imitate-next_permutation-bring-binary-search

    otherwise I search it myself:

    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int i,j;
            
            for(i = nums.size() - 1;i > 0 && nums[i-1] >= nums[i];i--);
            if (i)
            {
                for(j = nums.size() - 1; nums[j] <= nums[i-1];j--);
                swap(nums[i-1],nums[j]);
            }
            std::reverse(nums.begin() + i, nums.end());
        }
    };

Log in to reply
 

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