[LeetCode][python3]0031. Next Permutation

Start the journey
N2I -2020.09.01

1. My Solution

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums)<=1:
            return
        rec=0
        for i in range(len(nums)-2,-1,-1):
            if nums[i]<nums[i+1]:
                rec=i
                break
        swap=i
        for i in range(len(nums)-1,rec,-1):
            if nums[i]>nums[rec]:
                swap=i
                break
        if rec==swap:
            nums.sort()
            return
        # print(rec,swap)
        nums[rec]^=nums[swap]
        nums[swap]^=nums[rec]
        nums[rec]^=nums[swap]
        
        rec+=1
        swap=len(nums)-1
        while rec<swap:
            nums[rec]^=nums[swap]
            nums[swap]^=nums[rec]
            nums[rec]^=nums[swap]
            rec+=1
            swap-=1

Explanation:

An easy way to solve this problem. For this case, you have to think of this problem as “find the last ascending order pair of numbers in the array”. After you find it, swap the first number of that pair with the smallest ascending number behind it. Then you will get the next permutation array.

2. A faster Solution

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # from back to front, find the first descending num
        # swap the num with the smallest num larger than it from back
        # reverse all nums in the second half of the list
        for i in range(len(nums)-1,-1,-1):
            if i != 0:
                # first descending num
                if nums[i-1] < nums[i]:
                    break
        # entire list in descending order
        if i == 0:
            nums.reverse()
            return
        # one num to be swapped
        k = i - 1
        
        # the other num to be swapped
        for j in range(len(nums)-1,-1,-1):
            if nums[j] > nums[k]:
                break      
        # swap the numbers
        nums[j], nums[k] = nums[k], nums[j]
        # reverse the second portion of the list
        left, right = k+1, len(nums)-1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Explanation:

To reduce the cost time of this problem, you should avoid to use quick-sort the the first solution. Quick-sort will increase the cost time to run your code is this situation.