当前位置: 面试刷题>> 上一个排列 (经典算法题500道)


题目描述补充

给定一个数字序列,编写一个函数来找到它的上一个排列。一个数字序列的“上一个排列”是指通过重新排列其数字形成的字典序中前一个排列,并且每个数字仅能使用一次。如果不存在上一个排列,则返回空数组或根据语言特性返回相应的“空”表示。

例如,给定序列 [3,2,1],其上一个排列不存在,因此返回空数组 []null(根据编程语言)。给定序列 [3,1,2],其上一个排列是 [2,3,1]。给定序列 [1,3,2],其上一个排列是 [1,2,3]

注意

  1. 所有输入的数字都是唯一的。
  2. 输入的数组至少包含两个元素。

PHP 示例代码

function prevPermutation(&$nums) {
    $n = count($nums);
    // 从右向左找到第一个不满足递增的元素
    $i = $n - 2;
    while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) {
        $i--;
    }
    if ($i < 0) {
        // 已经是最小排列,返回空数组
        return [];
    }

    // 从右向左找到第一个比 nums[$i] 大的元素
    $j = $n - 1;
    while ($nums[$j] <= $nums[$i]) {
        $j--;
    }
    // 交换 nums[$i] 和 nums[$j]
    list($nums[$i], $nums[$j]) = array($nums[$j], $nums[$i]);

    // 反转 nums[$i+1] 到 nums[$n-1]
    $left = $i + 1;
    $right = $n - 1;
    while ($left < $right) {
        list($nums[$left], $nums[$right]) = array($nums[$right], $nums[$left]);
        $left++;
        $right--;
    }

    return $nums;
}

// 示例
$nums = [3, 2, 1];
prevPermutation($nums);
echo json_encode($nums); // 输出: []

$nums = [1, 3, 2];
prevPermutation($nums);
echo json_encode($nums); // 输出: [1,2,3]

Python 示例代码

def prevPermutation(nums):
    n = len(nums)
    i = n - 2
    # 从右向左找到第一个不满足递增的元素
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i < 0:
        return []

    # 从右向左找到第一个比 nums[i] 大的元素
    j = n - 1
    while nums[j] <= nums[i]:
        j -= 1
    # 交换 nums[i] 和 nums[j]
    nums[i], nums[j] = nums[j], nums[i]

    # 反转 nums[i+1:]
    nums[i + 1:] = reversed(nums[i + 1:])

    return nums

# 示例
nums = [3, 2, 1]
print(prevPermutation(nums))  # 输出: []

nums = [1, 3, 2]
print(prevPermutation(nums))  # 输出: [1, 2, 3]

JavaScript 示例代码

function prevPermutation(nums) {
    const n = nums.length;
    let i = n - 2;
    // 从右向左找到第一个不满足递增的元素
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i < 0) {
        // 已经是最小排列,返回空数组
        return [];
    }

    let j = n - 1;
    // 从右向左找到第一个比 nums[i] 大的元素
    while (nums[j] <= nums[i]) {
        j--;
    }
    // 交换 nums[i] 和 nums[j]
    [nums[i], nums[j]] = [nums[j], nums[i]];

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

    return nums;
}

// 示例
const nums = [3, 2, 1];
console.log(prevPermutation(nums)); // 输出: []

const nums2 = [1, 3, 2];
console.log(prevPermutation(nums2)); // 输出: [1, 2, 3]

码小课网站中有更多相关内容分享给大家学习,希望这些示例能帮助你更好地理解和解决问题。

推荐面试题