GeetCode Hub

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:

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

Example 2:

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

Example 3:

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

Example 4:

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

 

Constraints:

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

class Solution { public void nextPermutation(int[] nums) { if(nums.length <=1){ return; } int i=nums.length-2; for(;i>=0;i--){ if(nums[i] < nums[i+1]){ break; } } if(i==-1){ reverse(nums, 0, nums.length-1); return; } int j=nums.length-1; for(;j>=0;j--){ if(nums[j]>nums[i]){ break; } } swap(nums, i, j); reverse(nums, i+1, nums.length-1); } private void swap(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } private void reverse(int[] nums, int start, int end){ while(start < end){ swap(nums, start, end); start++; end--; } } }

Backward traverse the array until we find the two consecutive numbers such that nums[i] < nums[i + 1]. Because the numbers to the right of nums[i] are in descending order, so we can't make that part bigger.

Now we need to backward traverse the array again to find the first number nums[j] such that nums[j] > nums[i], and then swap them to generate a bigger number, as we need to generate the smallest permutation that is greater than the original number.

After swapping nums[i] and nums[j], we need to reverse the numbers to the right of nums[i] to force this part to be the smallest. Swapping nums[i] and nums[j] doesn't change the fact that the numbers to the right of nums[i] are still in descending order. So reversing this part can make its value smallest and meanwhile achieve O(N) time complexity. If we use sorting, then the complexity of this part will be O(NlogN).


Time complexity: O(N)
Space complexity: O(1)