问题描述
LeetCode 47. 全排列 II (opens in a new tab)，难度中等。
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
题解
按字典序排列
解题思路：
- 从后向前找到第一个降序元素
i。 - 如果找到，找到第一个大于
nums[i]的元素j，并交换nums[i]和nums[j]。 - 反转
i + 1到数组末尾的部分，使其成为最小字典序。 - 返回是否存在下一个排列。
Solution.java
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
// 确保初始排列是字典序最小的排列
Arrays.sort(nums);
do {
results.add(Arrays.stream(nums).boxed().toList());
} while (nextPermutation(nums));
return results;
}
public boolean nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2;
// 从后向前找到第一个降序元素 i
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
// 找到第一个大于 nums[i] 的元素 j，并交换 nums[i] 和 nums[j]
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
// 反转 i + 1 到数组末尾的部分，使其成为最小字典序
reverse(nums, i + 1, n - 1);
return i >= 0;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}