前言
本文介绍一种求有重复数字的全排列的去重思想，该算法思想在时间上优于目前使用最广泛的循环去重思想。
题目展示
参考题目：Acwing—递归实现排列型枚举II
参考题目：Leetcode—全排列II
因力扣的提交格式复杂，在这里用Acwing的题目做演示。
函数栈帧
若想了解该种思想，就要先知道什么是函数栈帧。
顾名思义，函数与栈和帧的结合，每调用一个函数就会在栈区上开辟一块空间，就像视频的每一帧一样，当函数调用结束后，这一帧也会随之销毁，在栈区开辟的空间也会还给操作系统。
如果我们在函数内部创建一个数组的话，每调用一次函数，就会创建一次这个数组，该数组只会保存在当前帧里，当函数调用结束，空间没了，这个数组自然也就没了。
f(int time)
{
int st[10];
f(time + 1);
}
int main()
{
fun(1);
return 0;
}如果你运行上面的代码，就会出现下面这样的情况：
由于函数的每一帧都在栈区内保存，所以后面的帧销毁之前，前面的帧内创建的st数组会一直保存，本文要介绍的思想就利用了函数栈帧的该种性质。
去重思想
这里先展示代码，随后进行详细解读。
全局变量与主函数 （与正常全排列无区别）
int N = 0;
int data[10];
int arr[10];
int used[10];
//...
int main()
{
scanf("%d", &N);
int i = 0;
for (i = 0; i < N; i++)
{
scanf("%d", &data[i]);
}
dfs(0);//递归用的函数
return 0;
}其中，N是数据的个数，data是保存数据的数组，arr是递归时保存每一帧状态的，used是记录某个数字是否被用过，这些变量与正常的全排列代码中的意义相同。
函数
为了观看方便，将用图片展示，与正常全排列代码不同之处已用红色标出。
在本题中，step代表当前要排列的位置的下标，若想去重，就要保证每个数在每个位置上只出现一次，同时还不能影响其他分支。
因此，我们在函数内部创建数组st，用来保存当前位置下有哪些数被用过了，被用过了就跳过这个数即可。
拿数据data10={1，1，3} 举例，第一个位置首先赋值为data0，同时让st[data0]+=1，表示在第一个位置data0 已经用过了，当第一个位置为data0 的分支全部结束后，就会把第一个位置赋为data1，但此时data0 和data1 相同，即st[data1] 和st[data0] 相同，都等于1，这样就把这第二个1给跳过了。
当我们进入到下一个位置时，又会创建一个新的st数组来保存当前位置的使用记录，这样前面的st数组既不会影响到后面的，也不会被后面的st数组覆盖，就能达到去重的效果。
错误示范
博主一开始并没有想到用函数栈帧的性质，而是创建一个10X10的全局数组，让每一行代表每个step（每个位置），每一列代表每个数，哪个位置的哪个数被用了，就让其自增1。
这样不就相当于有了十个一维数组，每个一位数组都代表每个位置的数，不也可以达成上文讲述的效果吗？
但是这样却忘记了一件事，数组的记录不能影响其他的分支，拿{1，1，3}举例。
下面将展示两张图，其中step代表位置，从上到下代表选择，每一个紫色框代表一帧
以上两张图便是一正确、一错误的两种方法最直观地解释了。
思想优劣
若是题目没有要求按照字典序输出，则这种思想与循环思想相比，最大的优势是不需要排序，节约了排序消耗的时间，降低了代码的复杂程度。
一般这种全排列题目，给定的N不会太大，所以排序的时间其实也很短，主要是降低了代码的复杂程度。
其次，即使题目要求按照字典序输出，该思想在时间上依然优于循环思想，Acwing上两种代码各提交十次去掉极值后取平均值，比循环思想快约20ms，几乎可以忽略不计。
由此得出：
- 题目不要求字典序——优先选用本文介绍的思想
- 题目要求字典序——两者皆可，差别不大
AC代码
下面展示Acwing的通过代码
#include<stdio.h>
#include<stdlib.h>
int n=0;
int arr[10];
int data[10];
int used[10];
f(int step)
{
int st[10]={0};
if(step==n)
{
int i=0;
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
return;
}
int i=0;
for(i=0;i<n;i++)
{
if(used[i]==0&&st[data[i]]==0)
{
used[i]=1;
st[data[i]]=1;
arr[step]=data[i];
f(step+1);
used[i]=0;
}
}
}
int cmp(const void* a,const void* b)
{
int* _a=(int*)a;
int* _b=(int*)b;
return *(_a)-*(_b);
}
int main ()
{
scanf("%d",&n);
int i=0;
for(i=0;i<n;i++)
{
scanf("%d",&data[i]);
}
qsort(data,n,4,cmp);
f(0);
return 0;
}感谢您的阅读与耐心~ 如有错误烦请指出~ 谢谢~
加载中,请稍侯......
网友评论