重复数字全排列的全新去重思想（非循环）C语言_全球最新

前言

本文介绍一种求有重复数字的全排列的去重思想，该算法思想在时间上优于目前使用最广泛的循环去重思想。

题目展示

参考题目：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#includeint 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