【C语言】浙大版C语言程序设计(第三版) 练习7-4 找出不是两个数组共有的元素

2024-01-07 19:57:20

前言

? ? 最近在学习浙大版的《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中无效值(重复值)计数+1
                break;            //并跳出内循环,去输入下一个元素
            }
    }//这样输入得到的数组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中无效值(重复值)计数+1
                break;            //并跳出内循环,去输入下一个元素
            }
    }//这样输入得到的数组b中没有重复值,全都是有效值,角标从0到nb-tb-1

    //3.计算出数组a的不共组元素,并打印输出
    count = 0;                //不共组元素的个数,初始化为0
    for(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;    //程序返回
}

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