首页 >编程 >正文

重复数字全排列的全新去重思想(非循环)C语言

前言

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


题目展示

重复数字全排列的全新去重思想(非循环)C语言

参考题目:Acwing—递归实现排列型枚举II

参考题目:Leetcode—全排列II

因力扣的提交格式复杂,在这里用Acwing的题目做演示。

函数栈帧

若想了解该种思想,就要先知道什么是函数栈帧。

顾名思义,函数与栈和帧的结合,每调用一个函数就会在栈区上开辟一块空间,就像视频的每一帧一样,当函数调用结束后,这一帧也会随之销毁,在栈区开辟的空间也会还给操作系统。

如果我们在函数内部创建一个数组的话,每调用一次函数,就会创建一次这个数组,该数组只会保存在当前帧里,当函数调用结束,空间没了,这个数组自然也就没了。

f(int time)
{
	int st[10];
	f(time + 1);
}
int main()
{
	fun(1);
	return 0;
}

如果你运行上面的代码,就会出现下面这样的情况:

重复数字全排列的全新去重思想(非循环)C语言

由于函数的每一帧都在栈区内保存,所以后面的帧销毁之前,前面的帧内创建的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是记录某个数字是否被用过,这些变量与正常的全排列代码中的意义相同

函数

为了观看方便,将用图片展示,与正常全排列代码不同之处已用红色标出。

重复数字全排列的全新去重思想(非循环)C语言

在本题中,step代表当前要排列的位置的下标,若想去重,就要保证每个数在每个位置上只出现一次,同时还不能影响其他分支

因此,我们在函数内部创建数组st,用来保存当前位置下有哪些数被用过了,被用过了就跳过这个数即可。

拿数据data10={1,1,3} 举例,第一个位置首先赋值为data0,同时让st[data0]+=1,表示在第一个位置data0 已经用过了,当第一个位置为data0 的分支全部结束后,就会把第一个位置赋为data1,但此时data0data1 相同,即st[data1]st[data0] 相同,都等于1,这样就把这第二个1给跳过了。

当我们进入到下一个位置时,又会创建一个新的st数组来保存当前位置的使用记录,这样前面的st数组既不会影响到后面的,也不会被后面的st数组覆盖,就能达到去重的效果。

错误示范

博主一开始并没有想到用函数栈帧的性质,而是创建一个10X10的全局数组,让每一行代表每个step(每个位置),每一列代表每个数,哪个位置的哪个数被用了,就让其自增1。

这样不就相当于有了十个一维数组,每个一位数组都代表每个位置的数,不也可以达成上文讲述的效果吗?

但是这样却忘记了一件事,数组的记录不能影响其他的分支,拿{1,1,3}举例。

下面将展示两张图,其中step代表位置,从上到下代表选择,每一个紫色框代表一帧

重复数字全排列的全新去重思想(非循环)C语言


重复数字全排列的全新去重思想(非循环)C语言

以上两张图便是一正确、一错误的两种方法最直观地解释了。

思想优劣

若是题目没有要求按照字典序输出,则这种思想与循环思想相比,最大的优势是不需要排序,节约了排序消耗的时间,降低了代码的复杂程度。

一般这种全排列题目,给定的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;
}

感谢您的阅读与耐心~ 如有错误烦请指出~ 谢谢~

网友评论

验证码 换一张
取 消
暂无评论...
三日内热门评论文章
关键词
为您推荐
  • 相关阅读
  • 业界资讯
  • 手机通讯
  • 电脑办公
  • 新奇数码
  • 软件游戏
  • 科学探索