Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

31. 下一个排列 #15

Open
webVueBlog opened this issue Sep 3, 2022 · 0 comments
Open

31. 下一个排列 #15

webVueBlog opened this issue Sep 3, 2022 · 0 comments

Comments

@webVueBlog
Copy link
Owner

31. 下一个排列

Description

Difficulty: 中等

Related Topics: 数组, 双指针

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

  • 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3][1,3,2][3,1,2][2,3,1]

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

  • 例如,arr = [1,2,3] 的下一个排列是 [1,3,2]
  • 类似地,arr = [2,3,1] 的下一个排列是 [3,1,2]
  • arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ,找出 nums 的下一个排列。

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

示例 1:

输入:nums = [1,2,3]
输出:[1,3,2]

示例 2:

输入:nums = [3,2,1]
输出:[1,2,3]

示例 3:

输入:nums = [1,1,5]
输出:[1,5,1]

提示:

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

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
// a[i-1] a[j]
var nextPermutation = function(nums) {
    const len = nums.length
    let i = len - 2
    // 找到第一个当前项比后一项小的位置
    while (i >= 0 && nums[i] >= nums[i+1]) i--
    // i>=0,说明此时不是最大的排序
    if (i >= 0) {
        let j = len - 1
        // 找到最小的比nums[i]大的数对应的j
        while (j > i && nums[i] >= nums[j]) j--
        // 交换位置
        [nums[i], nums[j]] = [nums[j], nums[i]]
    }
    // i后面的数升序排序
    let [left, right] = [i + 1, len - 1]
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]]
        left++
        right--
    }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant