Next Permutation Problem


Description

LeetCode Problem 31.

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

1
2
Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

1
2
Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

1
2
Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

1
2
Input: nums = [1]
Output: [1]

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n-2, tmp, j, k;
        
        while (i >= 0 && nums[i] >= nums[i+1]) i --;
        
        if (i >= 0) {
            k = n-1;
            while (k > i && nums[k] <= nums[i]) k --;
            tmp = nums[k];
            nums[k] = nums[i];
            nums[i] = tmp;
        }
        
        j = i+1, k = n-1;
        while (j < k) {
            tmp = nums[j];
            nums[j] = nums[k];
            nums[k] = tmp;
            j ++;
            k --;
        }
        return;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Pancake Sorting Problem

LeetCode 969. Given an array of integers arr, sort the...