目录
2023.5.3更新
1.序列中整数去重
前言
题目是来自于牛客网基础题中BC99题,卡了一段时间,写出来后看他人的题解有一些新的启发和思考。
描述
输入n个整数的序列,要求对这个序列进行去重操作。所谓去重,是指对这个序列中每个重复出现的整数,只保留该数第一次出现的位置,删除其余位置。
输入描述:
输入包含两行,第一行包含一个正整数n(1 ≤ n ≤ 1000),表示第二行序列中数字的个数;第二行包含n个整数(范围1~5000),用空格分隔。
输出描述:
输出为一行,按照输入的顺序输出去重之后的数字,用空格分隔。
示例1
输入:
5
10 12 93 12 75
输出:
10 12 93 75
看到题目第一想法是创建一个数组,输入值后遍历数组,把相同的都覆盖掉,但出现种种问题,不断修改有了下面的答案。
#include <stdio.h> int arr[1001]; int main() { int n; scanf("%d", &n); int cout = 0; for (int i = 0; i < n; i++) scanf("%d", &arr[i]); for (int i = 0; i < n-cout; i++) { for (int j = i + 1; j < n-cout; j++) { while (arr[i] == arr[j]) { for (int m = j; m < n - cout - 1; m++) arr[m] = arr[m + 1]; arr[n - 1 - cout] = -9999; cout++; } } } for (int i = 0; i < n - cout; i++) printf("%d ", arr[i]); return 0; }
显然这并不是好代码,写的很乱很杂乱无章,可读性不强,可以说只有写的人能看懂这是在干什么,但总归在在线OJ上通过所有的测试了,于是看了解题中有用两个数组的解法。
于是有了新的思路,创建两个数组,一个存储,另外一个识别上上一个数组中有用的留下,重复的删去,于是写了下面代码,但是是错误的,错误的,错误的!
//以下为错误代码: #include <stdio.h> int main() { int n, arr[1001], out[101], cout = 0, m = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); out[0] = arr[0]; m++; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (arr[i] != arr[j]) { out[m] = arr[i]; m++; break; } } } for (int i = 0; i <= m; i++) printf("%d ", out[i]); return 0; }
正确思路:
虽然有了好思路,但写的也并不对,于是看了别人的具体解题代码有了新的想法,其实第一个数组和第二个数组的存储数据并不一定是需要分开的,第一个数组在录入数据的同时,就可以判断是否有此数据,然后把新数据放到第二个数组里,再输出第二个数组即可,下面是正确的解题代码:
正确解题:
#include <stdio.h> int main() { int n,arr[101],out[101],cout=0,m=0; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&arr[i]); int flag=0; for(int j=0;j<i;j++) { if(arr[i]==out[j]) flag=1; } if(flag==0) { out[m++]=arr[i]; } } for(int i=0;i<m;i++) printf("%d ",out[i]); return 0; }
arr数组负责输入,out数组负责输出,第一个数组的存储和第二个数组的存储并不对立,可以在第一个数组的每一个元素输入后,就进行判断前面是否包含相同的元素,如果有就进行标记(这里我用的是flag进行标记),如果前面所有的元素都和新输入的元素不同,那么新输入的元素就可以保留进入out数组,最后记得变量初始化即可。
思考感悟:
题目中进行数组的输入并非一定要全部输入后再进行下一步操作,在每一个元素输入的过程中也是可以进行一些操作步骤的,以此题为例,如果在输入的过程中就进行判断,存储元素,那么不仅减小了代码量,增加了可读性,最重要的是避免了后续单独遍历数组读取有用数据进行存储这个过程中可能出现的问题。