删除两两相邻的重复数字 XDOJ 竞赛拓展 编号640

2024-01-02 14:28:43

给定 n (n < 10000) 个数字,删除两两相邻重复的数字后把剩余数字按原顺序输 出。

输入说明: 输入的第一个正整数表示数字个数 n(0 < n < 10000) ,随后为 n 个整数,整数之 间用空格或换行分隔。 输出说明: 删除两两相邻重复的整数后,把剩余整数按原顺序输出,整数之间用一个空格分 隔。若剩余整数为 0 个,则输出“NULL”。

样例输入 10 1 3 5 5 3 2 1 8 8 8

样例输出 1 2 1 8

说明: 1 3 5 5 3 2 1 8 8 8 (5 相邻重复)

删除相邻 5: 1 3 3 2 1 8 8 8 (3 相邻重复)

删除相邻 3: 1 2 1 8 8 8 (8 相邻重复)

删除相邻 8: 1 2 1 8 (无相邻重复 —— 输出答案


本题可以有多种思路。

我个人在接触本题时其实是看成了一道数组题,通过改变存入的位点来覆盖被删除的值,同时改变最终输出的元素个数——这样被删除部分如果在末尾无法被覆盖也就同样不需要考虑了。

利用输入数目恒定这一已知条件来决定输入阶段的结束 再于输出阶段按照n此时的大小决定输出情况。

其实在这种于顺序读入过程中进行处理的解决思路下,这个问题也可以戏称为“消消乐”——读入新的元素时如果重复则引发消除,并且每一次消除都会使(最终所输出的)总的个数减少两个;在特定情况下可以一直连续消除,直到没有“新方块”输入或者没有可以消除的原有“方块”为止。

做完之后查了查其他人的解决方式

这当中

Bitterlane wula前辈的文章(删除相邻的重复元素_一个数组去掉相邻元素的重复值-CSDN博客)中的“就地栈”的概念尤其让我受益匪浅,一下子茅塞顿开。归根结底刚刚接触各种ADT的我并没有充分理解它们的本质,我还需要进一步学习算法和数据结构的基础知识。

#include<stdio.h>
#include<stdlib.h>
int main(){
int n,i,count;
int* a;

scanf("%d",&n);
count=n;
a=(int*)malloc(n*sizeof(int));
//这里malloc是不担心时间的情况下用着玩的 
for(i=0;i<n;i++)
{
 if (i==0){
 scanf("%d",&a[0]);
 count--;}
else{	
 scanf("%d",&a[i]);
 count--;
 if(a[i]==a[i-1]){
  i=i-2;
  n=n-2;
  };
 if(n==0)
  break;
}
if(count==0)
 break;
}

if(n==0)
 printf("NULL");
else 
 if(n==1)
  printf("%d",a[0]);
 else
  {for(i=0;i<n-1;i++)
  printf("%d ",a[i]);
  printf("%d",a[n-1]);}
//这里是因为题目中的示例输出最后一个数字后面没有空格。其实本题不用在意这个 
 
free(a);

return 0;
 }

(我在开头调用malloc动态分配空间很大程度上是由于题目本身时间限制宽松。本题没有真正的动态调用需求,而且10000也并不是很大的数目,并不需要担心空间问题,为此降低执行效率并不是经济的选择(笑)。

文章来源:https://blog.csdn.net/qq_41932732/article/details/135326489
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。