性价比高的网站建设,做3d动画视频接私活的网站,潍坊昌大建设集团网站,展示型网站建设方案前言 最近在学习浙大版的《C语言程序设计》#xff08;第三版#xff09;教材#xff0c;同步在PTA平台上做对应的练习题。这道练习题花了比较长的时间#xff0c;于是就写篇博文记录一下我的算法和代码。 2024.01.03 题目
练习7-4 找出不是两个数组共有的元素
作者 张彤…前言 最近在学习浙大版的《C语言程序设计》第三版教材同步在PTA平台上做对应的练习题。这道练习题花了比较长的时间于是就写篇博文记录一下我的算法和代码。 2024.01.03 题目
练习7-4 找出不是两个数组共有的元素
作者 张彤彧
单位 浙江大学
给定两个整型数组本题要求找出不是两者共有的元素。
输入格式:
输入分别在两行中给出两个整型数组每行先给出正整数N≤20随后是N个整数其间以空格分隔。
输出格式:
在一行中按照数字给出的顺序输出不是两数组共有的元素数字间以空格分隔但行末不得有多余的空格。题目保证至少存在一个这样的数字。同一数字不重复输出。
输入样例:
10 3 -5 2 8 0 3 5 -15 9 100
11 6 4 8 2 6 -5 9 0 100 8 1输出样例:
3 5 -15 6 4 1 思路
1.思路
一开始我总想着找线性算法无果。后来想这道题涉及的数据规模比较小时间复杂度O(n^2) 也能接受。既然如此就直接暴力求解数组ab的元素挨个比较一遍O(n^2)的时间复杂度就来了只要发现有不重复的元素就打印输出。
但是题目还有一个要求输出的元素不能重复这就要求数组ab的本组元素之间不能重复。解决思路就是在输入一个数组元素的时候跟所有本组中已经存储的元素比较如果有重复值那么当前输入的元素就作废了是无效值。
2.步骤
①在输入数组ab的元素时对每一个元素都遍历本数组中已经输入的元素查找是否有重复值若有则当前元素为无效值不占用数组角标即被下一个元素覆盖。这样得到的数组ab应该都是没有重复值的数组。 ②然后遍历数组a每一个元素用内循环遍历数组b每个元素查找是否有重复值若有则跳出内循环若遍历完内循环仍然没有重复值则输出a[i]即不共组元素。 ③之后遍历数组b每个元素内循环遍历数组a每个元素同理输出数组b中的不共组元素。 代码
亲测可行通过所有测试点
#includestdio.h
int main(void){/*思路在输入数组ab的元素时对每一个元素都遍历本数组中已经输入的元素查找是否有重复值若有则当前元素不占用数组角标即被下一个元素覆盖。这样得到的数组ab应该都是没有重复值的数组。然后遍历数组a每一个元素用内循环遍历数组b每个元素查找是否有重复值若有则跳出内循环若遍历完内循环仍然没有重复值则输出a[i]即不共组元素。之后遍历数组b每个元素内循环遍历数组a每个元素同理输出数组b中的不共组元素。时间复杂度O(n^2)数据规模比较小也能接受。*/int i,j,na,nb,ta0,tb0,flag,count; //flag用于标记是否有重复值count计数不共组元素个数//ij用于数组角标na,nb是数组ab的元素个数ta,tb是数组ab中本组元素重复值即无效值的个数int a[20],b[20]; //待处理的数组//1.输入数组a的数据scanf(%d,na); //输入数组a的整数个数for(i0,ta0;ina;i){ //i计数输入元素的个数na-ta是数组a中有效元素个数scanf(%d,a[i-ta]); //输入编号为i的元素存放在数组a的i-ta角标处for(j0;ji-ta;j) //内循环遍历数组a中在此之前存储的所有元素if(a[i-ta]a[j]){ //若发现有重复值ta; //则数组a中无效值重复值计数1break; //并跳出内循环去输入下一个元素}}//这样输入得到的数组a中没有重复值全都是有效值角标从0到na-ta-1//2.输入数组b的数据 方法同上scanf(%d,nb); //输入数组b的整数个数for(i0,tb0;inb;i){ //i计数输入元素的个数nb-tb是数组b中有效元素个数scanf(%d,b[i-tb]); //输入编号为i的元素存放在数组b的i-tb角标处for(j0;ji-tb;j) //内循环遍历数组b中在此之前存储的所有元素if(b[i-tb]b[j]){ //若发现有重复值tb; //则数组b中无效值重复值计数1break; //并跳出内循环去输入下一个元素}}//这样输入得到的数组b中没有重复值全都是有效值角标从0到nb-tb-1//3.计算出数组a的不共组元素并打印输出count 0; //不共组元素的个数初始化为0for(i0;ina-ta;i){ //遍历数组a中的每个元素flag 0; //数组a的当前元素是否与数组b中某个元素重复默认0为不重复for(j0;jnb-tb;j){ //与数组b中每个元素依次比较if(a[i]b[j]){ //若有重复值flag 1; //则标记一下有重复值 break; //并跳出内循环继续处理下一个数组a的元素}}if(flag 0){ //若把数组b所有元素都比较完毕仍未发现重复值则要输出这个不共组元素if(count0) //如果这是要输出的第一个元素count 1; //标记一下以后的元素就不再是第一个元素了else //如果在此之前已经有输出过元素了printf( ); //先输出一个空格作为分隔符printf(%d,a[i]); //把这个不共组元素打印输出}}//4.计算出数组b的不共组元素并打印输出 方法同上 for(i0;inb-tb;i){ //遍历数组b中的每个元素flag 0; //数组b的当前元素是否与数组a中某个元素重复默认0为不重复for(j0;jna-ta;j){ //与数组a中每个元素依次比较if(b[i]a[j]){ //若有重复值flag 1; //则标记一下有重复值 break; //并跳出内循环继续处理下一个数组b的元素}}if(flag 0){ //若把数组a所有元素都比较完毕仍未发现重复值则要输出这个不共组元素if(count0) //如果这是要输出的第一个元素count 1; //标记一下以后的元素就不再是第一个元素了else //如果在此之前已经有输出过元素了printf( ); //先输出一个空格作为分隔符printf(%d,b[i]); //把这个不共组元素打印输出}}return 0; //程序返回
}
