LeetCode——下一个排列

小咪咪 2022-05-16 06:35 192阅读 0赞

**题目**：

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

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

必须**[原地][Link 1]**修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。  
`1,2,3` → `1,3,2`  
`3,2,1` → `1,2,3`  
`1,1,5` → `1,5,1`

**思想**：

题目是要求找个下一个更大的排列，但是这个排列必须是大于当前排列中的排列中最小的排列，这时候通过观察示例发现，我们只需要从末尾开始遍历然后找到不是最小的数与前面更小的数交换就可以，这也是为什么示例是3个数的原因，比较容易发现规律。如果只是找到从末尾找到大一点的数，和前面小一点的数交换，还不行，必须对交换位置后的数进行排序。

简单来讲，首先找到交换的位置，位置是有两个位置，因为是两个数交换，一个靠前的位置changeindex1，一个靠后的位置changeindex2。找到了以后，我们要将changeindex1后面的数进行从小到大的排列。如何找到交换的位置呢，我们要保证changeindex1尽量靠后，changeindex2的数字尽量小。

**代码**：

class Solution:
        def nextPermutation(self, nums):
            """
            :type nums: List[int]
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            numsCnt = len(nums)
            changeIndex1 = -1 #交换节点较前的那个位置
    
            changeIndex2 = numsCnt-1 # 交换节点较后的那个个位置
            index1 = numsCnt-1 #主动交换的数，即后面的那个数的位置
            while index1 >=0:#从末尾向前遍历
                index2 = index1#被动交换的数
                while index2 >=0:
                    if nums[index2] < nums[index1]:#z找到第一个可以交换的数
                        if index2 > changeIndex1:#交换的位置更靠后
                            changeIndex1 = index2
                            changeIndex2 = index1
                        elif index2 == changeIndex1:#如果交换位置相同
                            if nums[changeIndex2] > nums[index1]:
                                print( nums[changeIndex2])
                                changeIndex2 = index1
                        break #找到了第一个可以交换的数就可以跳出第一个循环了
                    index2 -=1
                index1 -=1
            if changeIndex1 != -1: #找到了交换点
                nums[changeIndex1],nums[changeIndex2] = nums[changeIndex2],nums[changeIndex1]
                index1 = changeIndex1+1
                while index1<numsCnt-1:#对changeindex1后面的数进行排序
                    index2 = index1+1
                    while index2 < numsCnt:
                        if nums[index1] > nums[index2]:
                            nums[index1],nums[index2] = nums[index2],nums[index1]
                        index2 +=1
                    index1+=1
            else:#没有找到交换点，则返回最小的排列
                index1 = 0
                while index1 < numsCnt - 1:
                    index2 = index1 + 1
                    while index2 < numsCnt :
                        if nums[index1] > nums[index2]:
                            nums[index1], nums[index2] = nums[index2], nums[index1]
                        index2+=1
                    index1+=1
            return nums#为了方便测试，所以返回nums
    
    
    if __name__ =="__main__":
        res = Solution()
        print(res.nextPermutation([1,3,2]));
        pass

[Link 1]: https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95