10 lines C++ (12ms), swap two numbers, reverse tail


  • 2
    N
    class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            if (nums.size() < 2) return;
        
            int front = nums.size();
            while (--front > 0) {
                if (nums[front] > nums[front - 1]) {
                    int back = nums.size();
                    while (nums[--back] <= nums[front - 1]) {}
                    swap(nums[front - 1], nums[back]);
                    break;
                }
            }
            // faster than sort, because the tail must be in descending order.
            reverse(nums.begin() + front, nums.end());
        }
    };

Log in to reply
 

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