郑州旅游网站建设,源码网站跟自己做的网站区别,凡客诚品失败的主要原因,都江堰网站建设公司文章目录 47. 全排列 II题目描述回溯算法 47. 全排列 II
题目描述
给定一个可包含重复数字的序列 nums #xff0c;按任意顺序 返回所有不重复的全排列。
示例 1#xff1a; 输入#xff1a;nums [1,1,2] 输出#xff1a; [[1,1,2], [1,2,1], [2,1,1]] 示例 2#xff… 文章目录 47. 全排列 II题目描述回溯算法 47. 全排列 II
题目描述
给定一个可包含重复数字的序列 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
回溯算法
class Solution {
public:vectorvectorint permuteUnique(vectorint nums) {// 为了方便地检测重复先将数组排序sort(nums.begin(), nums.end());// 使用一个布尔数组来标记哪些数字已经被使用过了vectorbool used(nums.size(), false);// 调用回溯函数来搜索所有排列backtracking(nums, used);// 返回最终的结果集return result;}private:vectorvectorint result; // 用于存放最终的排列结果vectorint path; // 用于存放当前路径即当前的排列// 回溯函数void backtracking(vectorint nums, vectorbool used) {// 如果当前路径的长度等于nums的长度则表明这是一个完成的排列if (path.size() nums.size()) {result.push_back(path); // 将当前路径加入到结果集中return; // 结束当前递归}// 遍历nums尝试每一种可能for (int i 0; i nums.size(); i) {// 如果当前数字已经被使用过或者是一个重复的排列则跳过if (used[i] || (i 0 nums[i] nums[i - 1] !used[i - 1])) {continue;}// 将当前数字标记为已使用used[i] true;// 将当前数字加入到当前路径path.push_back(nums[i]);// 继续递归填下一个数backtracking(nums, used);// 回溯撤销上一个操作used[i] false; // 将当前数字标记为未使用path.pop_back(); // 从当前路径移除当前数字}}
};这段代码使用了回溯法搜索所有可能的排列。关键点在于如何避免重复的排列
在开始任何操作前数组先被排序这使得相同的数字都相邻从而更容易检测重复。使用一个布尔数组used来标记哪些数字已经被放入当前路径中。当尝试填入一个数字到路径时如果这个数字和前一个数字相同并且前一个数字没有被使用过即当前的数字和前一个数字在原数组中是相邻的则跳过这个选项。这是因为前一个数字在当前位置生成的排列已经被考虑过了。
此算法能够高效地生成所有不重复的排列其时间复杂度取决于生成的排列数目以及每个排列的长度但由于使用了剪枝策略避免了不必要的搜索提高了效率。
