当前位置： 面试刷题>> 上一个排列 (经典算法题500道)
**题目描述补充**：
给定一个数字序列，编写一个函数来找到它的上一个排列。一个数字序列的“上一个排列”是指通过重新排列其数字形成的字典序中前一个排列，并且每个数字仅能使用一次。如果不存在上一个排列，则返回空数组或根据语言特性返回相应的“空”表示。
例如，给定序列 `[3,2,1]`，其上一个排列不存在，因此返回空数组 `[]` 或 `null`（根据编程语言）。给定序列 `[3,1,2]`，其上一个排列是 `[2,3,1]`。给定序列 `[1,3,2]`，其上一个排列是 `[1,2,3]`。
**注意**：
1. 所有输入的数字都是唯一的。
2. 输入的数组至少包含两个元素。
**PHP 示例代码**：
```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 示例代码**：
```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 示例代码**：
```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]
```
**码小课网站中有更多相关内容分享给大家学习**，希望这些示例能帮助你更好地理解和解决问题。