打卡群刷题总结0628——下一个排列

题目：31. 下一个排列

链接：https://leetcode-cn.com/problems/next-permutation

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

解题：

1、找规律：1）从右往前遍历，找到第一个nums[i-1] < nums[i]的元素；2）从i及以后的元素中找到刚好大于nums[i-1]的元素，和nums[i-1]进行交换；3）将i及以后的元素进行排序。

代码：

代码语言：javascript复制

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # 找到nums[i] < nums[i   1]
        start_index = len(nums) - 1
        while start_index > 0 and nums[start_index - 1] >= nums[start_index]:
            start_index -= 1


        if start_index > 0:
            start_index -= 1
            end_index = len(nums) - 1
            while nums[end_index] <= nums[start_index]:
                end_index -= 1
            nums[start_index], nums[end_index] = nums[end_index], nums[start_index]
            start_index  = 1

        # 排序
        end_index = len(nums) - 1
        while start_index < end_index:
            nums[start_index], nums[end_index] = nums[end_index], nums[start_index]
            start_index  = 1
            end_index -= 1

PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。

PPS：还是得日更呀，总结一下总是好的。

0 人点赞