【LeetCode #47 题解】带重复全排列 II（递归回溯法、非递归实现）-白红宇的个人博客

【LeetCode #47 题解】带重复全排列 II（递归回溯法、非递归实现）

发布日期：2021-06-29 14:55:06 浏览次数：3 分类：技术文章

本文共 3550 字，大约阅读时间需要 11 分钟。

【LeetCode #47 题解】带重复全排列 II（递归回溯法、非递归实现）

本LeetCode 算法系列文章分类导航：《》
本文链接：《》

题目：

题目链接：《》

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:输入: [1,1,2]输出:[  [1,1,2],  [1,2,1],  [2,1,1]]

题解一：非递归实现

本题解思路主要如下：

先对数组进行从小到大排序。

接着对它不停的求下排列，直到找不到下一排列为止。

有关下一排列思路，可参考：《》

class Solution {
   public:    void print(vector
   
     &nums){
           for(int i=0; i

> permuteUnique(vector

& nums) {

vector

> res; // 1. 对数组先排序 sort(nums.begin(), nums.end()); res.emplace_back(nums); print(nums); // 2. 对它不停的求下排列，直到找不到下一排列为止 while(1){

int pos = nums.size() - 1; // pos 指向最后一个数的下标 cout << pos<< endl; // 找到最右边的第一个非升续的数，如：1 4 6 5 4 3 中的 4 while(pos > 0 && nums[pos] <= nums[pos-1]){

pos--; cout << pos<< endl; } if(pos > 0){

printf("找到第一个数pos[%d]=%d ", pos-1, nums[pos-1]); // 找到了，此时找到剩下的数字中第一个比它大的数, 如 6 5 4 3 中的 5 比 4 大 int big = nums.size()-1; while(big >= pos && nums[big] <= nums[pos-1]) big--; printf(", 第二个数pos[%d]=%d, 交换\n", big, nums[big]); swap(nums[big], nums[pos-1]); }else{

break; // 找不到下一排列后，说明已经找完，此时 break退出 } // 对剩余的数进行反续 reverse(nums.begin() + pos, nums.end()); print(nums); res.emplace_back(nums); } return res; }};

提交结果：

题解二：递归回溯法

本题解思路就是在《【》的递归方法基础上，增加了去重的操作。

去重的思路如下：

如果要交换的数不是同一个数(i != first), 并且这两个数相等，说明当前数是重复的，需要丢弃。
如： 2，2，3，4中的两个 2 ，这种情况，交换第一个数和第二个数后的结果是重复的，之前统计过了，因此需要丢序。

如果要交换的数和前一个相等
如： 2，3，3，4 中，当要交换 2 和第二个3 时，交换后的结果在交换2 和第一个3 时统计过了，是重复的，因此需要丢弃。

每次交换之后，需要做一个拷贝，对剩余的数进行从小到大排序
如： 2，2，2，3，3，4，5，当要交换第一个 2 和 5 时，交换后的结果是 5，2，2，3，3，4，2
由于后面的 2，2，3，3，4，2 排序是乱序的，接下来递归对它找下一排列，就没法找全，还会出现重复的情况
（1）第一个2 与自身交换，此时数组有交；
（2）第一个2 与第二个2交换时，根据前面的规则 1，两数相等，数组丢弃；
（2）第一个2 与第三个2 交换时，这时就出现漏洞了，它同时满足前的规则1 和规则2，但数组同样无交。
因此为出现这种情况，就需要用到递归中的局部变量，对它做一个拷贝，将剩下的数进行排序。
使用排序过后的拷贝数组继续递归归

class Solution {
   public:    void print(vector
   
     &nums){
           for(int i=0; i

> &res, vector

& nums, int first, int size){

if(first == size){

//cout << "入栈：===>"; print(nums); res.emplace_back(nums); return; }else{

for(int i = first; i

first+1 && nums[i] == nums[i-1])){

//cout << " first=" << first << " i=" << i << " continue ->";print(nums); continue; } //cout << " first=" << first << " i=" << i << " ->" ; swap(nums[i], nums[first]); // 交换 // 由于交换后的数，可能会导致后面数字顺序错乱，导致出现重复的情况，如下两种。 // 如： 2,0,-1,1,0,1,-1 中交换第3个数和第 4 个数结果为 2,0,1,-1,0,1,-1 // 而： 2,0,1,-1,-1,1,0 中交换第3个数和第 4 个数结果为 2,0,1,-1,0,1,-1 // 所以此处需要先做一份拷贝，对first 之后的数进行从小到大排序，每次交换前的数据都是有序的，避免了出现此种情况 vector

tmp(nums); sort(tmp.begin() + first+1, tmp.end()); back_trace(res, tmp, first+1, size); swap(nums[i], nums[first]); // 还原 } } } vector

> permuteUnique(vector

& nums) { vector

> res; sort(nums.begin(), nums.end()); back_trace(res, nums, 0, nums.size()); return res; }};

提交结果：

转载地址：https://ciellee.blog.csdn.net/article/details/109272009 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【车机xxx视频需求实现 2】 - 车内DMS/AVR/ROA三个摄像头虚拟化代码实现

下一篇：【车机xxx视频需求实现 1】 - 需求分析及实现思路（车内DMS/AVR/ROA摄像头）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！