国家开放大学网站界面设计,建设银行天津分行网站,怎样建设企业网站 用于宣传,网站空间排行榜1. 题目链接#xff1a;47. 全排列 II
2. 题目描述#xff1a; 给定一个可包含重复数字的序列 nums #xff0c;按任意顺序 返回所有不重复的全排列。 示例 1#xff1a; 输入#xff1a;nums [1,1,2]
输出#xff1a;
[[1,1,2],[1,2,1],[2,1,1]]示例 2#xff1a; 输…1. 题目链接47. 全排列 II
2. 题目描述 给定一个可包含重复数字的序列 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 3. 解法
3.1 算法思路
因为题目不要求返回的排列顺序因此我们可以对初始化状态排序将所有相同的元素放在各自相邻的位置方便之后操作。因此重复元素的存在我们可以选择元素进行全排列时可能会存在重复排列
我们可以将相同的元素按照排序后的下标顺序出现在排序中通俗来讲若元素s出现x次则排序后的第2个元素s一定出现在第1个元素是后面第3个元素s一定出现在第2个元素s后面以此类推此时的全排列一定不会出现重复结果例如a11a21a32排序结果为[1,1,2]的情况只有一次即a1在a2的前面因为a2不会出现在a1前面从而避免了重复排列我们在每一个位置上考虑所有可能情况并且不会重复注意若当前元素的前一个相同元素出现在当前状态中则当前元素也不能直接放入当前状态的数组此做法可以保证相同元素的排列顺序与排序后的相同元素的排序相同即避免了重复排列出现通过深度优先搜索的方法不断地枚举每个数在当前位置的可能性并在递归结束时回溯到上一个状态直到枚举所有可能性得到正确的结果
3.2 递归流程 定义一个二维数组ret用来存放所有可能的排列一个一维数组path用来存放每个状态的排列一个一维数组check标记元素然后从第一个位置开始进行递归 一个一维数组check标记元素然后从第一个位置开始进行递归 在每个递归的状态中我们维护一个步数pos表示当前已经处理了几个数字 在每个递归状态中枚举所有下标i若这个下标未被标记并且在它之前的相同元素被标记过则使用nums数组中当前下标的元素 将check[i]标记为1将 nums[i]添加至path数组末尾对第 pos1个位置进行递归对 check[i]重新赋值为0并且删除path末尾元素表示回溯 最后返回ret
3.3 C算法代码
class Solution {vectorint path; // 用于存储当前排列的路径vectorvectorint ret; // 用于存储所有满足条件的排列组合bool check[9]; // 用于记录每个元素是否已经被使用过public:vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end()); // 对输入数组进行排序以便后续剪枝操作dfs(nums, 0); // 调用深度优先搜索函数开始生成排列return ret; // 返回所有满足条件的排列组合}void dfs(vectorint nums, int pos) {if (pos nums.size()) { // 如果已经遍历完所有元素说明找到了一个合法的排列ret.push_back(path); // 将当前排列添加到结果中return;}for (int i 0; i nums.size(); i) {// 剪枝操作如果当前元素已经被使用过或者与前一个元素相同且前一个元素未被使用过则跳过该元素if (!check[i] (i 0 || nums[i] ! nums[i - 1] || check[i - 1])) {path.push_back(nums[i]); // 将当前元素添加到当前排列中check[i] true; // 标记当前元素为已使用dfs(nums, pos 1); // 继续递归生成下一个元素的排列path.pop_back(); // 回溯操作移除当前元素恢复上一层的状态check[i] false; // 标记当前元素为未使用}}}
};
