leetcode 31 temp

leetcode_31.py

#-*- coding: utf-8 -*-

def nextPermutation(nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    '''
    for i in range(len(nums)-1, 0, -1):
        if nums[i] < nums[i-1]:
            swap = nums[i-1]
            for j in range(i, len(nums)):
                if swap > nums[j]:
                    nums[i-1], nums[j] = nums[j], swap
    return nums
    '''
    i = len(nums) - 2
    while i >= 0 and nums[i+1] <= nums[i]:
        i -= 1

    if i >= 0:
        j = len(nums) - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        nums = swap(nums, i, j)

    nums = reverse(nums, i+1)
    return nums


def reverse(nums, start):
    i, j = start, len(nums) - 1
    while i < j:
        swap(nums, i, j)
        i += 1
        j -= 1
    return nums


def swap(nums, i, j):
    temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
    return nums


if __name__ == '__main__':
    print(nextPermutation(nums=[1,2,3])) #[1,3,2]
    print(nextPermutation(nums=[3,2,1])) #[1,2,3]
    print(nextPermutation(nums=[5,7,9,8,6])) #[5,8,6,7,9]
    print(nextPermutation(nums=[9,5,4,3,2,1])) #[1,2,3,4,5,9]
    print(nextPermutation(nums=[1,5,8,4,7,6,5,3,1])) #[1,5,8,5,1,3,4,6,7]

def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # find longest non-increasing suffix
        right = len(nums) - 1
        while nums[right] <= nums[right-1] and right-1 >= 0:
            right -= 1
        
        if right == 0:
            return self.reverse(nums,0,len(nums)-1)
        
        # find pivot
        pivot = right-1
        successor = 0
        
        # find rightmost succesor
        for i in range(len(nums)-1,pivot,-1):
            if nums[i] > nums[pivot]:
                successor = i
                break
        
        # swap pivot and successor
        nums[pivot],nums[successor] = nums[successor],nums[pivot]  
        
        # reverse suffix
        self.reverse(nums,pivot+1,len(nums)-1)
        return nums
        
    def reverse(self,nums,l,r):
        while l < r:
            nums[l],nums[r] = nums[r],nums[l]
            l += 1
            r -= 1
        return nums

def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 1
        lastnum = -1
        after_max_num = None
        max_point =None
        while True:
            thisnum = nums[i] 
            if thisnum >= lastnum:
                lastnum = thisnum
            else:
                after_max_num = thisnum
                max_point = i+1
                break
            i -= 1
            if i < 0:
                break
        if after_max_num is not None:
            arr = []
            for index,x in enumerate(nums[max_point:]):
                arr =  [x] + arr
                if x > after_max_num:
                    target_index = index
                else:
                    pass
            arr[index-target_index] = nums[max_point-1]
            nums[max_point-1],nums[max_point+target_index] = nums[max_point+target_index],nums[max_point-1]
            xnums = nums[:max_point] + arr
            for index,x in enumerate(xnums): 
                nums[index] = x
        else:
            xnums = nums
            for index,x in enumerate(xnums[::-1]): 
                nums[index] = x