Leetcode题库——31.下一个排列

@author: ZZQ

@software: PyCharm

@file: nextPermutation.py

@time: 2018/11/12 15:32

要求：

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

思路：从数组尾部向前搜索，找到第一次nums[i] 比nums[i+1]小的位置，

将该位置i记录下来，然后将该位置之后的所有元素进行排列，找到比nums[i]大的第一个元素，将两数交换即可。

class Solution():

    def __init__(self):

        pass

    def quickSort(self, list, left, right):

        if left > right:

            return

        middle_value = list[left]

        i = left

        j = right

        while i < j:

            while i < j and list[j] >= middle_value:

                j -= 1

            while i < j and list[i] <= middle_value:

                i += 1

            if i < j:

                t = list[i]

                list[i] = list[j]

                list[j] = t

        list[left] = list[i]

        list[i] = middle_value

        self.quickSort(list, left, i-1)

        self.quickSort(list, i+1, right)

    def nextPermutation(self, nums):

        """

        :type nums: List[int]

        :rtype: void Do not return anything, modify nums in-place instead.

        """

        nums_len = len(nums)

        index = 0

        small_value = -1

        if nums_len == 0:

            return nums

        for i in range(nums_len-1):

            if nums[nums_len-1-i-1] < nums[nums_len-1-i]:

                index = nums_len-1-i

                small_value = nums[nums_len-1-i-1]

                break

        if small_value == -1:

            nums.sort(reverse=False)

            return nums

        self.quickSort(nums, index, nums_len-1)

        for j in range(index, nums_len):

            if nums[j] > small_value:

                t = nums[j]

                nums[j] = nums[index-1]

                nums[index-1] = t

                break

        return nums

巴特西

Leetcode题库——31.下一个排列

最新文章

热门文章