PTA-找出不是两个数组共有的元素

  • 时间:
  • 浏览:
  • 来源:互联网

练习7-4 找出不是两个数组共有的元素 (20 分)

给定两个整型数组,本题要求找出不是两者共有的元素。

输入格式:

输入分别在两行中给出两个整型数组,每行先给出正整数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

C语言实现:

1、不使用指针

#include <stdio.h>

int main(){
	
	int m, n;
	//输入第一个数组 r
	scanf("%d", &m);
	int r[m];
	for(int i = 0; i <= m - 1; i++)
		scanf("%d", &r[i]);
	//输入第二个数组 s
	scanf("%d", &n);
	int s[n];
	for(int i = 0; i <= n - 1; i++)
		scanf("%d", &s[i]);
	//对数组r的每一个元素r[i],为其设置一个标记flag(初始化为0)
	//把数组s中与r[i]相等的元素s[j]赋值为一个极大值1e+6 
	//并且每当数组s中有一个元素s[j]与r[i]相等,flag+1
	//遍历完数组s后,如果r[i]的flag>0
	//就把数组r中的r[i]以及r[i]后面与r[i]相等的所有r[k]也赋值为极大值1e+6 
	for(int i = 0; i <= m - 1; i++) {
		int flag = 0;
		for(int j = 0; j <= n - 1 ; j++) {
			if( r[i] == s[j] ) {
				s[j] = 1e+6;
				flag++;
			}
		}
		if( flag > 0 ) {
			for(int k = i + 1; k <= m - 1; k++)
				if( r[k] == r[i] )
					r[k] = 1e+6;
			r[i] = 1e+6;
		}
	}
	//经过上一步,数组r和数组s的公共元素都被置为1e+6,剩下的即为非公共元素,最多m+n个 
	//但在数组r和数组s的内部,可能还存在 重复(相等)的元素
	//现在把数组r和数组s剩下的元素合并到一个新的数组t中
	int t[m+n], count = 0;
	// 把数组r中的非1e+6元素加入到数组t中 
	for(int i = 0; i <= m - 1; i++)
		if( r[i] != 1e+6 )
			t[count++] = r[i];
	// 把数组s中的非1e+6元素加入到数组t中,加入完成后,count即为剩余的总元素个数 
	for(int i = 0; i <= n - 1; i++)
		if( s[i] != 1e+6 )
			t[count++] = s[i];
	//初步判断,如果只有一个元素,直接输出(不需要加空格) 
	if( count == 1 )
		printf("%d\n", t[0]);
	//如果剩余的元素大于1个 
	//数组t中可能存在重复的元素 
	else {
		int count2 = 0;//count2统计需要删除的重复的元素个数
		//对数组t的第1个至倒数第二个元素,把它后面与它相等的元素置为1e+6 
		for(int i = 0; i <= count - 2; i++) {
			if( t[i] == 1e+6 )
				continue;
			for(int j = i + 1; j <= count - 1; j++) {
				if( t[i] == t[j] ) {
					t[j] = 1e+6;
					count2++;
				}
			}
		}
		//经过上一步,把数组t中多余的、重复的元素置为了1e+6
		//把剩余的元素((count - count2)个)放到一个新数组u中
		int u[count-count2];
		int count3 = 0;
		for(int i = 0; i <= count - 1; i++) {
			if( t[i] != 1e+6 )
				u[count3++] = t[i];
		}
		//初步判断,如果只有一个元素,直接输出(不需要加空格) 
		if( count3 == 1 )
			printf("%d\n", u[0]);
		//如果>1个元素,前count3 - 1个元素+空格输出
		//最后一个换行输出 
		else {
			for(int i = 0; i <= count3 - 2; i++)
				printf("%d ", u[i]);
			printf("%d\n", u[count3-1]);
		}
	}
	return 0;
}

2、使用指针:

#include<stdio.h>

void solve(int* a, int* b, int n, int m, int* pre, int* cur){
    for(int i = 0; i < n; ++i){
        int f = 0;
        for(int j = 0; j < i; ++j)
            if(a[i] == a[j]){
                f = 1;
                break;
            }
        if(f) continue;
        for(int j = 0; j < m; ++j){
            if(a[i] == b[j]){
                --*cur;
                break;
            }
        }
        if(*cur == *pre){
            if(*pre) printf(" ");
            printf("%d", a[i]);
            *pre = ++*cur;
        }
        else *cur = *pre;
    }
}

int main(){
    int n,m,pre = 0,cur = 0;
    int a[25],b[25];
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    for(int i = 0; i < m; ++i){
        scanf("%d", &b[i]);
    }
    solve(a, b, n, m, &pre, &cur);
    solve(b, a, m, n, &pre, &cur);
    return 0;
}

本文链接http://www.dzjqx.cn/news/show-617159.html