题目描述补充

题目：下一个排列Ⅱ

给定一个整数数组 nums，你可以将数组重新排列以得到一个新的数组，新数组是由原数组中的元素组成的所有可能排列的字典序中的下一个排列。然而，这次题目有一个额外的限制：数组中可能包含重复的元素。你需要找到这样的下一个排列，并且保证得到的数组是唯一的（在字典序中）。

注意：

• 必须原地修改数组，即直接修改输入数组 nums，而不是创建一个新的数组。
• 如果不存在下一个排列，则数组必须保持不变并返回空数组。

示例

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

输入：nums = [3,2,1] 输出：[]（因为不存在下一个排列）

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

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

解题思路

1. 从右向左找到第一个相邻的元素对 (i, i+1)，使得 nums[i] < nums[i+1]。如果找不到这样的元素对，则说明整个数组是降序排列的，即已经是最大的排列，不存在下一个排列，直接返回空数组或原数组。
2. 从右向左找到第一个大于 nums[i] 的元素 nums[j]。
3. 交换 nums[i] 和 nums[j]。
4. 将索引 i+1 及其之后的元素进行升序排序（因为这些元素在之前的步骤中可能是降序的，需要调整为升序以得到最小的下一个排列）。

PHP 代码示例

function nextPermutation(&$nums) {
    $n = count($nums);
    if ($n <= 1) return;

    $i = $n - 2;
    while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) {
        $i--;
    }
    if ($i < 0) {
        // 整个数组是降序的，没有下一个排列
        rsort($nums);
        return [];
    }

    $j = $n - 1;
    while ($j > $i && $nums[$j] <= $nums[$i]) {
        $j--;
    }
    // 交换 nums[i] 和 nums[j]
    $temp = $nums[$i];
    $nums[$i] = $nums[$j];
    $nums[$j] = $temp;

    // 反转 i+1 及其之后的数组
    $left = $i + 1;
    $right = $n - 1;
    while ($left < $right) {
        $temp = $nums[$left];
        $nums[$left] = $nums[$right];
        $nums[$right] = $temp;
        $left++;
        $right--;
    }
}

Python 代码示例

def nextPermutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i < 0:
        nums.reverse()
        return

    j = n - 1
    while j > i and nums[j] <= nums[i]:
        j -= 1
    nums[i], nums[j] = nums[j], nums[i]
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left, right = left + 1, right - 1

JavaScript 代码示例

function nextPermutation(nums) {
    const n = nums.length;
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i < 0) {
        nums.reverse();
        return;
    }

    let j = n - 1;
    while (j > i && nums[j] <= nums[i]) {
        j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];

    let left = i + 1, right = n - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}

码小课：以上给出了PHP、Python和JavaScript三种语言的代码实现，这些代码都遵循了相同的算法思路。在码小课网站中，你可以找到更多关于算法和数据结构的相关内容，帮助你深入学习并提升编程能力。