31.Next Permutation

Tag: [permutation], [swap], [trick], [reverse]

Hard: [###]

Link: https://leetcode.com/problems/next-permutation/#/description

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

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

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3→1,3,2
3,2,1→1,2,3
1,1,5→1,5,1

Better Solution:

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums or len(nums) == 1:
            return

        size = len(nums)
        index = size - 1 - 1
        while index >= 0 and nums[index] >= nums[index + 1]:
            index -= 1

        if index < 0:
            self.reverse(nums, 0, size - 1)
            return

        left = index
        right = size - 1
        while left < right and nums[left] >= nums[right]:
            right -= 1

        nums[left], nums[right] = nums[right], nums[left]
        self.reverse(nums, left + 1, size - 1)

    def reverse(self, arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1

Revelation:

• First, scan from right to left side, find the first nums[i] < nums[i + 1], so i is left.
• Then, scan from right to left side, find the first nums[left] < nums[right].
• Then swap nums[left] and nums[right], then reverse nums[left + 1:]

Note:

• Time complexity = O(n), n is the number of elements in nums.

Solution:

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if not nums or len(nums) == 1:
            return

        size = len(nums)
        for left in xrange(size - 1 - 1, -1, -1):
            for right in xrange(size - 1, left, -1):
                if nums[left] < nums[right]:
                    nums[left], nums[right] = nums[right], nums[left]
                    self.reverse(nums, left + 1, size - 1)
                    return

        self.reverse(nums, 0, size - 1)

    def reverse(self, arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1

Revelation:

• 我们想找到一对left, right, nums[left] < nums[right]，但是想尽可能的让left和right更靠右侧.

Note:

• Time complexity = O(n^2), n is the number of elements in nums.