## 去重题目以及去重排序题目总结
最近离谱张同学,做了些去重类的题目,有一些新的感悟以及思考心得,这里全部分享给大家,
（由于其他博主也发表过相关博客,这里张同学借鉴了些,如果冒犯,立即删除）
我们可以先看这样一道题:如图所示（本题均选自鹏哥刷题课的题目）
如果要大家做的话,会怎么做呢？大家思考一下（10min）
其实这种题目大致有这么几种思路：
第一种:标记法:就是把要去重的元素,标记为-1或者你喜欢的符号,然后最后循环打印的时候,就打印不是标记的元素就好啦
第二种:覆盖法(输入的数字如果和前面的重复了,那就删除,重新输入,这个操作我们看不到,但是实际上有。
方法1:标记法
思路:输入输出都很好表示,关键就是for循环中的if判断该咋弄?我们可以这样想：
既然是要比较元素,那我用两层for循环来用,比如我要比较1 1 2 2 3 3,那我的第一次for循环来遍历下标为0到4的元素,那就是1 1 2 2 3第一个元素与第二个1 2 2 3进行比较,第二个1与2 2 3 来进行比较,这样等到了最后的2的时候,我们与最后一个3进行比较就好了，如果叙述不清楚的话，下面如图所示。
for(i=1;i<n-1;i++)//这里的i=0,i<n-1就是上面的例子,1 1 2 2
{
for(j=i+1;j<n;j++)//而j=1+i,j<n就是第一次是五个元素,1 2 2 4 5,第二次是4个元素
{
if(a[j]==a[i])
{
a[j]=-1;//把要重复的元素来标记为-1就好
}
}
}
这样整体思路是不是就有了呢？
然后我们转化为代码的形式就好了啦
#include<stdio.h>
int main()
{
int n=0,i=0,j=0,arr[100005];
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
//去重的关键点:标记法
for(i=0;i<n-1;i++)//这里的i=0,i<n-1就是上面的例子,1 1 2 2 4
{
for(j=i+1;j<n;j++)
//而j=i+1,j<n就是后五个元素,1 2 2 4 5
//===============================================
//j=i+1;就是从1开始，向后的去比较元素,这个点一定要注意
//================================================
{
if(arr[j]==arr[i])
{
arr[j]=-1;//把要重复的元素来标记为-1就好
}
}
}
//去重完成之后打印出来
for(i=0;i<n;i++)
{
if(arr[i]!=-1)//切记一定要是==不是一个=,我已经在这里出过很多次错误了
printf("%d ",arr[i]);
}
return 0;
}
方法2:覆盖法(输入的数字如果和前面的重复了,那就删除,重新输入,这个操作我们看不到,但是实际上有。
其实可以这样来进行理解：n=5,输入1 2 3 3 2
咱们第一个位置输一，第二个位置输二，第三个位置输三，当i等于四的时候，你应该输第四个元素，我输了一个三跟前面的三相同，所以i--，变成三了，然后你执行下一次循环的时候，循环要执行表达式三，i++变成了4，那么你要重新输入第四个位置的元素，你又输了一个二，然后输入二跟前面又相同了，所以i--又变成了三，这样的话。你看你输的数据是12332，这五个数据都输入了，但是因为后面的三和二跟前面的相同，所以在输第四个位置的时候，你输了一个三,变量i退回去了,变成3，然后你又输了一个二的时候，它又退回去了，所以你最终的数据还是一二三.那n减减就是一开始是5，然后发现两个重复的，第一次发现重复的n－－变成4，第二次发现2也是重复的，然后n－－变成了3，所以在最后打印的时候，就变成了1到3循环.
#include<stdio.h>
int main()
{
int a[2001];
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
for(j=1;j<i;j++)
{
if(a[j]==a[i])
{
i=i-1;
n=n-1;
}
}
}
for(i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
方法三:覆盖法的盗版(1),但是这种覆盖法只能弄连续的数字,无法在乱序中找到并且去重,(牛客上过不了)但是这个思路很好
针对于这个点我们可以这样想:先上代码啦
for(i=0;i<n-1;i++)
{
if(a[i]==a[i+1])
{
for(j=i+1;j<n-1;j++)//j=i+1的原理同上题一样,还有下面的a[j]=a[j+1]都是后面的元素往前移动,需要注意点是移动完之后,后面的元素不变喔
{
a[j]=a[j+1];
}
}
}
eg:1 1 2 2 3 3，这样的是可以的,1 4 3 5 3这样不行
/*里面的for循环一定要写好是,a[j]=a[i],不是a[i]=a[j]
,因为这层for循环的循环变量是j,如果是i的话,每次只能循环一次,
eg:
元素:1 1 2 2 3 3
下标:0 1 2 3 4 5
第一次for(i=0;i<5;i++) for(j=1;j<6;j++)
a[0]与a[1],a[2],a[3],a[4],a[5]依次进行比较如果后面有重复的,就标记为-1,以便后面进行打印
第二次for(i=1;i<5;i++) for(j=2;j<6;j++)
a[1] 与a[2],a[3],a[4],a[5].依次进行比较,如有相同,标记为-1
第三次for(i=3;i<5;i++) for(j=4;j<6;j++)
a[3]与a[4],a[5],a[6].依次进行比较,同上
第四次for(i=4;i<5;i++) for(j=5;j<6;j++)
a[4]与a[5],a[6].依次进行比较,同上
第五次:i=5不满足条件,循环终止,
总结,for循环是前5个元素,分别与后面的除了这次元素的所有元素依次进行比较,所以for循环条件为for(i=0;i<n-1;i++)
第二层for循环条件为for(j=i+1;j<n;j++)
本题关键点就是这个,剩下的就剩下打印啦
好，这个方法用于扩展思路，实际难想，且操作性不怎么强，饭后品味挺好的。
完整代码如下（已经在编译器上测试过，没问题）
#include <stdio.h>
int main()
{
//覆盖法去重;只能去有序序列
int a[100005],n=0,j=0,i=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
if(a[i]==a[i+1])
{
for(j=i+1;j<n-1;j++)//j=i+1的原理同上题一样,还有下面的a[j]=a[j+1]都是后面的元素往前移动,需要注意点是移动完之后,后面的元素不变喔
{
a[j]=a[j+1];
}
}
}
for(i=0;i<n;i++)
{
if(i>0 && a[i-1]==a[i])
{
break;
}
printf("%d ",a[i]);
}
return 0;
}
好，这是去重部分，然后咱们看下一个，那就是去重排序了。
题目奉上：
去重排序,既然是排序>那就得,排序完,再去重,因为这样顺序的话,比较好弄一点,
简而言之就是双层for循环,加一个去重的小判 断
首先,需要输入n个数字,老朋友了,直接一个for循环就ok
int a[100005],n=0,j=0,i=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
而排序的话,可以采用快速排序(qsort),或者冒泡排序,
本期只简单介绍一下快排以及冒泡的使用规则,详细算法分析后期会给出
首先冒泡排序:
1确定元素个数:n,以及确定趟数,eg10个元素排序要进行9趟冒泡排序
2确定每趟两两交换的最大次数,j<n-1-i,那为什么要-i呢？比如第一趟,j<n-1,要进行n-1次交换,那么第二趟的话还是n-1次,第三趟还是n-1>这样明显不对,所以得用一个变量i来进行每次的改正
3在交换的过程中,如果第一个比第二个大,需要创建一个临时变量来进行交换
好啦,然后转化为代码就可以
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
int t=0;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
然后快排(今天只讲如果应用，具体详细的做法后面会有介绍)
库函数,得引一个头文件#include <stdlib.h>
qsort的四个参数:
1:存放的是带排序数据中第一个对象的地址–arr
2:排序数据的元素个数–sz
3:排序数据中一个元素的大小,单位是字节–sizeof(arr[0])
4:用来比较带排序数据中2个元素的函数。–cmp_int(比较整形元素)
#include <stdio.h>
#include <stdlib.h>
//用qsort来排序数字
int cmp_int(const void*e1,const void*e2)
{
return *(int*)e2-*(int*)e1;
}
int main()
{
int arr[]={1,2,3,4};
int sz=sizeof(arr) / sizeof(arr[0]);
int i=0;
qsort(arr,sz,sizeof(arr[0]),cmp_int);
for(i=0;i<sz;i++)
{
printf("%d ",arr[i]);
}
return 0;
}
//第一种情况倒序顺拍为升序可以，是e1-e2了
//乱序也可以拍为升序e1-e2
//乱序排降序==是e2-e1
//升序排降序==是e2-e1
好了，排序先介绍到这里，然后就可以和上面的进行组合啦。
方法一:标记去重排序(用冒泡来排)(已经在牛客网测试过,可以)
#include<stdio.h>
int main()
{
int arr[100005],n=0,j=0,i=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
//排序
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(arr[j]>arr[j+1])
{
int t=0;
t=arr[j];
arr[j]=arr[j+1];
arr[j+1]=t;
}
}
}
//去重
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[j]==arr[i])
arr[j]=-1;
}
}
for(i=0;i<n;i++)
{
if(arr[i]!=-1)
printf("%d ",arr[i]);
}
return 0;
}
方法二:快排标记去重(已经在牛客网上测试过，可以)
#include <stdio.h>
#include <stdlib.h>
//用qsort来排序数字
int cmp_int(const void*e1,const void*e2)
{
return *(int*)e1-*(int*)e2;
}
int main()
{
int n=0,arr[1000];
scanf("%d",&n);
//输入
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
//快排
int i=0,j=0;
qsort(arr,n,sizeof(arr[0]),cmp_int);
//去重
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[j]==arr[i])
arr[j]=-1;
}
}
//打印
for(i=0;i<n;i++)
{
if(arr[i]!=-1)
printf("%d ",arr[i]);
}
return 0;
}
然后是覆盖法去重
#include <stdio.h>
int main()
{
//覆盖法去重
int a[100005],n=0,j=0,i=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
int t=0;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=0;i<n-1;i++)
{
if(a[i]==a[i+1])
{
for(j=i+1;j<n-1;j++)//j=i+1的原理同上题一样,还有下面的a[j]=a[j+1]都是后面的元素往前移动,需要注意点是移动完之后,后面的元素不变喔
{
a[j]=a[j+1];
}
}
}
for(i=0;i<n;i++)
{
if(i>0 && a[i-1]==a[i])
{
continue;//还可以换成break;但不知道为什么，希望兄弟们可以给小弟指出来
}
printf("%d ",a[i]);
}
}
覆盖快排去重(可以通过)
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void*e1,const void*e2)
{
return *(int*)e1-*(int*)e2;
}
int main()
{
//覆盖法去重
int a[100005],n=0,j=0,i=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
//快排来排序
qsort(a,n,sizeof(a[0]),cmp_int);
//去重
for(i=0;i<n-1;i++)
{
if(a[i]==a[i+1])
{
for(j=i+1;j<n-1;j++)//j=i+1的原理同上题一样,还有下面的a[j]=a[j+1]都是后面的元素往前移动,需要注意点是移动完之后,后面的元素不变喔
{
a[j]=a[j+1];
}
}
}
//打印
for(i=0;i<n;i++)
{
if(i>0 && a[i-1]==a[i])
{
continue;//还可以换成break;但不知道为什么
}
printf("%d ",a[i]);
}
return 0;
}
好啦，今天的总结就到这里啦。 本次总结还有很多的不足与缺点，希望各位大佬，兄弟姐妹们可以顺手指出来，谢谢大家啦