1. 首页

LeetCode 031. 下一个排列

题目描述

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

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

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

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

难度:Middle

前置知识

  • 回溯法

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

符合直觉的方法是按顺序求出所有的排列,如果当前排列等于 nums,那么我直接取下一个但是这种做法不符合 constant space 要求(题目要求直接修改原数组),时间复杂度也太高,为 O(n!),肯定不是合适的解。

这种题目比较抽象,写几个例子通常会帮助理解问题的规律。我找了几个例子,其中蓝色背景表示的是当前数字找下一个更大排列的时候需要改变的元素.

31.next-permutation

我们不难发现,蓝色的数字都是从后往前第一个不递增的元素,并且我们的下一个更大的排列
只需要改变蓝色的以及之后部分即可,前面的不需要变。

那么怎么改变蓝色的以及后面部分呢?为了使增量最小,
由于前面我们观察发现,其实剩下的元素从左到右是递减的,而我们想要变成递增的,我们只需要不断交换首尾元素即可。

另外我们也可以以回溯的角度来思考这个问题,让我们先回溯一次:

31.next-permutation-2

这个时候可以选择的元素只有2,我们无法组成更大的排列,我们继续回溯,直到如图:

31.next-permutation-3

我们发现我们可以交换4或者2实现变大的效果,但是要保证变大的幅度最小(下一个更大),
我们需要选择最小的,由于之前我们发现后面是从左到右递减的,显然就是交换最右面大于1的。

之后就是不断交换使之幅度最小:

31.next-permutation-4

关键点解析

  • 写几个例子通常会帮助理解问题的规律
  • 在有序数组中首尾指针不断交换位置即可实现reverse
  • 找到从右边起第一个大于nums[i]的,并将其和nums[i]进行交换

代码

语言支持: Javascript,Python3

JavaScript Code:

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
 * @lc app=leetcode id=31 lang=javascript
 *
 * [31] Next Permutation
 */

function reverseRange(A, i, j) {
  while (i < j) {
    const temp = A[i];
    A[i] = A[j];
    A[j] = temp;
    i++;
    j--;
  }
}
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  // 时间复杂度O(n) 空间复杂度O(1)
  if (nums == null || nums.length <= 1) return;

  let i = nums.length - 2;
  // 从后往前找到第一个降序的,相当于找到了我们的回溯点
  while (i > -1 && nums[i + 1] <= nums[i]) i--;

  // 如果找了就swap
  if (i > -1) {
    let j = nums.length - 1;
    // 找到从右边起第一个大于nums[i]的,并将其和nums[i]进行交换
    // 因为如果交换的数字比nums[i]还要小肯定不符合题意
    while (nums[j] <= nums[i]) j--;
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

  // 最后我们只需要将剩下的元素从左到右,依次填入当前最小的元素就可以保证是大于当前排列的最小值了
  // [i + 1, A.length -1]的元素进行反转

  reverseRange(nums, i + 1, nums.length - 1);
};

Python3 Code:

class Solution:
    def nextPermutation(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        :param list nums
        """
        # 第一步,从后往前,找到下降点
        down_index = None
        for i in range(len(nums)-2, -1, -1):
            if nums[i] < nums[i+1]:
                down_index = i
                break
        # 如果没有下降点,重新排列
        if down_index is None:
            nums.reverse()
        # 如果有下降点
        else:
            # 第二步,从后往前,找到比下降点大的数,对换位置
            for i in range(len(nums)-1, i, -1):
                if nums[down_index] < nums[i]:
                    nums[down_index], nums[i] = nums[i], nums[down_index]
                    break
            # 第三部,重新排列下降点之后的数
            i, j = down_index+1, len(nums)-1
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

Python3 Code:

class Solution:
    def nextPermutation(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        :param list nums
        """
        # 第一步,从后往前,找到下降点
        down_index = None
        for i in range(len(nums)-2, -1, -1):
            if nums[i] < nums[i+1]:
                down_index = i
                break
        # 如果没有下降点,重新排列
        if down_index is None:
            nums.reverse()
        # 如果有下降点
        else:
            # 第二步,从后往前,找到比下降点大的数,对换位置
            for i in range(len(nums)-1, i, -1):
                if nums[down_index] < nums[i]:
                    nums[down_index], nums[i] = nums[i], nums[down_index]
                    break
            # 第三步,重新排列下降点之后的数
            i, j = down_index+1, len(nums)-1
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

相关题目

更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 031. 下一个排列

链接:https://www.javascriptc.com/4391.html

« LeetCode 032. 最长有效括号
Nginx 入门实战»
Flutter 中文教程资源

相关推荐

QR code