找数

C++ 中等 GESP五级真题 #排序#二分查找

题面描述

给定一个包含个互不相同的正整数的数组与一个包含个互不相同的正整数的数组，请你帮忙计算有多少数在数组与数组中均出现。

第一行包含两个整数。

第二行包含个正整数表示数组。

第三行包含个正整数表示数组。

输出一个整数，表示在数组与数组中均出现的数的个数。

输入：

3 5
4 2 3
3 1 5 4 6

输出：

样例1中，4、3在数组与中均出现。

对于40%的数据，保证。

对于100%的数据，保证，。

1.0 s

512.0 MB

💡 查看提示（先自己想一想再看）

本题考察排序与二分查找的结合应用。首先将其中一个数组排序，然后遍历另一个数组的每个元素，在已排序的数组中进行二分查找判断是否存在，可将时间复杂度控制在$O(n\log n + m\log n)$，满足1e5数据规模的时间要求。注意二分查找的边界处理，避免死循环或漏判元素。

⚙ 开始做这道题 0 人做过 · 0 收藏 · 4 浏览