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

Valid Palindrome Problem

LeetCode 125. A phrase is a palindrome if, after converting...

Remove Duplicates from Sorted List II Problem

LeetCode 82. Given the head of a sorted linked list,...

Remove Duplicates from Sorted Array II Problem

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

Partition List Problem

LeetCode 86. Given the head of a linked list and...

Merge Sorted Array Problem

LeetCode 88. You are given two integer arrays nums1 and...

Sort Colors Problem

LeetCode 75. Given an array nums with n objects colored...