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

给定 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也并不是很大的数目，并不需要担心空间问题，为此降低执行效率并不是经济的选择（笑）。