基础-入门综合题目讲解

经验分享区
1

T447834查找数字题解

题目大意

在 b 数组中找出 a 数组的数。

算法思路

既然是查找，就可以用循环暴力。首先要保证复杂度。

复杂度分析：

2 层循环嵌套： O(T(n^2+m^2)) 。带入 n,m,T 最大值 100 得 O(100(100^2+100^2))=O(2000000)=O(2 \times 10^6) 远远小于 4 \times 10^8 不会超。

所以放心暴力枚举。

暴力枚举

一共有 2 种状态，分别为找到 1 和没找到 0 ，所以定义 flag 变量初始值设 0 ，当找到就设为 1 。最后输出 flag 。

我们要在数组 b 中找数组 a 中的数，先考虑找一个，找多个就自然而然了。

要找的数为 a_i 则循环判断数 b_j ，定义循环 j 遍历数组 b ，从 1 到 m 步长为 1 。如果 a_i=b_j 则找到，让 flag 等于 1 ，等循环结束输出 flag 就行。

此部分的代码为：

		for(int i=1;i<=n;i++){
			int flag=0;
			for(int j=1;j<=m;j++){
				if(a[i]==b[j]){
					flag=1;
				}
			}
			cout<<flag<<" ";
		}

代码（code）

		for(int i=1;i<=n;i++){
			int flag=0;
			for(int j=1;j<=m;j++){
				if(a[i]==b[j]){
					flag=1;
				}
			}
			cout<<flag<<" ";
		}

AC 记录：删掉了，不让发。

2 个赞