Skip to content

31. Next Permutation

https://leetcode.com/problems/next-permutation/

js
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  var i = nums.length - 2
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--
  }

  if (i < 0) {
    nums.sort((a, b) => a - b)
    return
  }

  var j = i + 1
  while (j < nums.length && nums[j] > nums[i]) {
    j++
  }
  j--

  var temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp

  for (var k = 0; k < (nums.length - i) / 2 >> 0; k++) {
    temp = nums[i + k + 1]
    nums[i + k + 1] = nums[nums.length - k - 1]
    nums[nums.length - k - 1] = temp
  }
}
py
class Solution(object):

    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                break
        else:
            nums.reverse()
            return

        for j in range(len(nums) - 1, i, -1):
            if nums[j] > nums[i]:
                nums[i], nums[j] = nums[j], nums[i]
                break

        for j in range(0, (len(nums) - i) // 2):
            a, b = i + j + 1, len(nums) - j - 1
            nums[a], nums[b] = nums[b], nums[a]