Skip to content

Latest commit

 

History

History
211 lines (157 loc) · 6.46 KB

31.Next_Permutation.md

File metadata and controls

211 lines (157 loc) · 6.46 KB
  1. Next Permutation

中等

https://leetcode.cn/problems/next-permutation/

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

  • For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

  • For example, the next permutation of arr = [1,2,3] is [1,3,2].
  • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
  • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

相关企业

  • Facebook|57
  • 亚马逊 Amazon|21
  • 字节跳动|17
  • 微软 Microsoft|12
  • 谷歌 Google|8
  • 苹果 Apple|6
  • 彭博 Bloomberg|4
  • 甲骨文 Oracle|4
  • 优步 Uber|3
  • 高盛集团 Goldman Sachs|2

相关标签

  • Array
  • Two Pointers

相似题目

  • Permutations 中等
  • Permutations II 中等
  • Permutation Sequence 困难
  • Palindrome Permutation II 中等

sol 1 solve all subsets and match

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return 

        numsLeng = len(nums)
        # numsstr = ''.join(str(x) for x in nums)发现不用转化为str就能工作
        numsSorted = sorted(nums)
        results = []
        self.dfs(numsSorted, [], [], results, numsLeng)
        results = sorted(results)
        # print(results)
        resultsLeng = len(results)

        for i in range(resultsLeng):
            # currStr = ''.join(str(x) for x in results[i])
            # if currStr == numsstr:
            if results[i] == nums:
                if i + 1 < resultsLeng:
                    # nextStr = ''.join(str(x) for x in results[i+1])
                    # if nextStr != currStr:
                    if results[i+1] != results[i]:
                        for j in range(numsLeng):                    
                            nums[j] = results[i+1][j]
                        break
                elif i + 1 == resultsLeng:
                    for j in range(numsLeng):                    
                        nums[j] = results[0][j]
                    break

    def dfs(self, nums, currsebset, visited, results, numsLeng):
        if len(currsebset) == numsLeng:
            if currsebset not in results:
                results.append(list(currsebset))
                return

        for i in range(numsLeng):
            if i in visited:
                continue
            currsebset.append(nums[i])
            visited.append(i)
            self.dfs(nums, currsebset, visited, results, numsLeng)
            visited.pop()
            currsebset.pop()

sol 2

idea 有点tricky，而且一堆+1-1的小细节。 不推荐

规律

任何set或subset，

  • 如果内部元素是升序，则为所有permutations中排序最小的
    • 如 1 2 3 4，
    • 最小的permutation为1234
  • 如果内部元素是降序，则为所有permutations中排序最小的
    • 最大的permutation为4321

方法

  1. 从后往前寻找不是递增的下标i
  • 从后往前遍历数组，如果一直是逐渐增大的，则已经是最大的了，如果出现了一个下降的数，那么遍历就到此为止，因为这已遍历的部分就可以排列成下一个较大的数了

比如[ 1 11 12 4 7 6 5 3 2 ] 发现找到 i为3 ， a[3]=4就不是递增了

当找到这个突然下降的点A后，由于它后面已经排列为“最大”，因为A后面是完全降序的降序

在例子里 就是 7 6 5 3 2 降序

然后从i 往后找到比下标i 对应的数字大的 且值最小的那个，令它为k， 发现 k为6，a[6]=5 是比4大的，而且还是5还是最小的一个

交换i k 交换完毕 序列成了

1 11 12 5 7 6 4 3 2

这样的序列已经比原序列大了

然后把从 i+1 到 整个数组最后一个, 反转(就是对那几个元素排序) 1 11 12 5 2 3 4 6 7

这样既能保证比原序列大，而且i+1到结尾原本是降序的，说明是最大的排列，现在成了升序 i+1到结尾这一部分就成了最小的排列了

既能保证比原序列大，还尽可能的小，所以是原序列的下一个排列

如果一直没有找到下降的点，则全部逆转即可。（从完全的降序改为了升序）

复杂度分析

  • 时间复杂度 因为要遍历一遍数组 所以是O(N)的

  • 空间复杂度 没有新开辟空间，所以还是O(1)

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return

        divide_index = -1
        for i in range(len(nums)-1, 0, -1):
            if nums[i-1] >= nums[i]: #从后往前，找到第一个非增
                continue
            divide_index = i - 1
            break

        # >=0 说明nums不是完全降序的. 需要找到nums[divide_index]的 最小大于它的值
        if divide_index >= 0:
            minvalue, minvalue_index = nums[divide_index+1], divide_index+1
            for i in range(divide_index+1, len(nums)):
                if nums[i] > nums[divide_index] and nums[i] < minvalue:
                    print(111)
                    minvalue = nums[i]
                    minvalue_index = i
            # swap
            nums[divide_index], nums[minvalue_index] = nums[minvalue_index], nums[divide_index]

        # swap之后，后面的反向递增（正向递减）（最大permu）要改为 反向递减（正向递减）（最小permu）
        subset = list(nums[divide_index+1:])
        subset = sorted(subset)
        for i in range(divide_index+1, len(nums)):
            nums[i] = subset[i-divide_index-1]