【C语言】浙大版C语言程序设计(第三版) 练习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中的不共组元素。
代码
亲测可行，通过所有测试点！
#include<stdio.h>
int main(void){/*思路：在输入数组ab的元素时，对每一个元素都遍历本数组中已经输入的元素，查找是否有重复值，若有，则当前元素不占用数组角标，即被下一个元素覆盖。这样得到的数组ab应该都是没有重复值的数组。然后，遍历数组a每一个元素，用内循环遍历数组b每个元素，查找是否有重复值，若有，则跳出内循环；若遍历完内循环仍然没有重复值，则输出a[i]，即不共组元素。之后遍历数组b每个元素，内循环遍历数组a每个元素，同理，输出数组b中的不共组元素。时间复杂度O(n^2)，数据规模比较小，也能接受。*/int i,j,na,nb,ta=0,tb=0,flag,count; //flag用于标记是否有重复值，count计数不共组元素个数//ij用于数组角标，na,nb是数组ab的元素个数，ta,tb是数组ab中本组元素重复值（即无效值）的个数int a[20],b[20]; //待处理的数组//1.输入数组a的数据scanf("%d",&na); //输入数组a的整数个数for(i=0,ta=0;i<na;i++){ //i计数输入元素的个数，na-ta是数组a中有效元素个数scanf("%d",&a[i-ta]); //输入编号为i的元素，存放在数组a的i-ta角标处for(j=0;j<i-ta;j++) //内循环，遍历数组a中在此之前存储的所有元素if(a[i-ta]==a[j]){ //若发现有重复值ta++; //则数组a中无效值（重复值）计数+1break; //并跳出内循环，去输入下一个元素}}//这样输入得到的数组a中没有重复值，全都是有效值，角标从0到na-ta-1//2.输入数组b的数据 方法同上scanf("%d",&nb); //输入数组b的整数个数for(i=0,tb=0;i<nb;i++){ //i计数输入元素的个数，nb-tb是数组b中有效元素个数scanf("%d",&b[i-tb]); //输入编号为i的元素，存放在数组b的i-tb角标处for(j=0;j<i-tb;j++) //内循环，遍历数组b中在此之前存储的所有元素if(b[i-tb]==b[j]){ //若发现有重复值tb++; //则数组b中无效值（重复值）计数+1break; //并跳出内循环，去输入下一个元素}}//这样输入得到的数组b中没有重复值，全都是有效值，角标从0到nb-tb-1//3.计算出数组a的不共组元素，并打印输出count = 0; //不共组元素的个数，初始化为0for(i=0;i<na-ta;i++){ //遍历数组a中的每个元素flag = 0; //数组a的当前元素是否与数组b中某个元素重复，默认0为不重复for(j=0;j<nb-tb;j++){ //与数组b中每个元素依次比较if(a[i]==b[j]){ //若有重复值flag = 1; //则标记一下，有重复值 break; //并跳出内循环，继续处理下一个数组a的元素}}if(flag == 0){ //若把数组b所有元素都比较完毕仍未发现重复值，则要输出这个不共组元素if(count==0) //如果这是要输出的第一个元素count = 1; //标记一下，以后的元素就不再是第一个元素了else //如果在此之前已经有输出过元素了printf(" "); //先输出一个空格作为分隔符printf("%d",a[i]); //把这个不共组元素打印输出}}//4.计算出数组b的不共组元素，并打印输出 方法同上 for(i=0;i<nb-tb;i++){ //遍历数组b中的每个元素flag = 0; //数组b的当前元素是否与数组a中某个元素重复，默认0为不重复for(j=0;j<na-ta;j++){ //与数组a中每个元素依次比较if(b[i]==a[j]){ //若有重复值flag = 1; //则标记一下，有重复值 break; //并跳出内循环，继续处理下一个数组b的元素}}if(flag == 0){ //若把数组a所有元素都比较完毕仍未发现重复值，则要输出这个不共组元素if(count==0) //如果这是要输出的第一个元素count = 1; //标记一下，以后的元素就不再是第一个元素了else //如果在此之前已经有输出过元素了printf(" "); //先输出一个空格作为分隔符printf("%d",b[i]); //把这个不共组元素打印输出}}return 0; //程序返回
}