简答题
适中
#24885
找数 时间限制:1.0 s 内存限制:512.0 MB 题目描述 给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B,请你帮忙计算有…
找数
时间限制:1.0 s
内存限制:512.0 MB
题目描述
给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B,请你帮忙计算有多少数在数组A与 数组B中均出现。
输入格式
第一行包含两个整数n,m。
第二行包含n个正整数a1,a2,...,an表示数组A。
第二行包含m个正整数b1,b2,...,bn表示数组B。
输出格式
输出一个整数,表示在数组A与 数组B中均出现的数的个数。
输入样例
3 5 4 2 3 3 1 5 4 6
输出样例
2
样例解释
样例 1 中,4、3在数组 与 中均出现。
数据范围
对于40%的数据,保证1≤n,m≤1000。
对于100%的数据,保证1≤n,m≤105,1≤ai,bi≤109。
答案与解析
正确答案:<pre class="brush:python;toolbar:false;"># 接收a,b数组的大小以及数组内容
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
ans = 0
# 遍历b中的每一个数
for x in b:
l, r = 0, n - 1
# 二分查找a中是否包含x
while l < r:
mid = (l + r) // 2
# 如果a[mid]<x,则x一定在mid+1之后
if a[mid] < x:
l = mid + 1
else:
r = mid
if a[l] == x:
ans += 1
print(ans)</pre>
这道题暂未补解析。