Python solution doesn't require extra memory. 58ms.


  • 0
    S

    list.sort() and qsort() are used because sorted() is not in-place sort.

        def nextPermutation(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            i = len(nums)-1
            # find position i which i-1th element is less than ith element
            while i > 0 and nums[i-1] >= nums[i]:
                i -= 1
            # if nums is sorted in descending order, return sorted array in ascending order
            if i == 0:
                nums.sort()
            else:
                # sort i to end
                self.qsort(nums, i, len(nums)-1)
                # switch i-1 and smallest one bigger than i-1th element
                j = i
                while j < len(nums) and nums[j] <= nums[i-1]:
                    j += 1
                if j < len(nums) and nums[j] > nums[i-1]:
                    nums[j], nums[i-1] = nums[i-1], nums[j]
        # qsort implementation in python
        def partition(self, nums, begin, end):
            pivot = begin
            for i in range(begin+1,end+1):
                if nums[i] <= nums[begin]:
                    pivot += 1
                    nums[i], nums[pivot] = nums[pivot], nums[i]
            nums[pivot], nums[begin] = nums[begin], nums[pivot]
            return pivot
        def qsort(self, nums, begin, end):
            if begin >= end:
                return
            pivot = self.partition(nums, begin, end)
            self.qsort(nums, begin, pivot-1)
            self.qsort(nums, pivot+1, end)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.