http://acm.hdu.edu.cn/showproblem.php?pid=3763

题意:

两组数据

看重复的有多少

如果每输入一个就去查找的话O(n^2) 会超时

所以可以用二法

第一组数据输入

然后第二组数据输入 在第一组数据用二分查 这样O(n*logn)

不能用set等容器 虽然时间复杂度是一样的但是 MLE

还有一种O(n)的做法

枚举a数组中的元素,然后用一个指针指向b数组中第一个大于等于a数组当前元素的数,不断移动这个指针即可

 #include <iostream>
#include <stdio.h> using namespace std; int a[];
int b[];
int n;
bool search(int x)
{
int l = , r = n-;
int mid = (l+r)/;
while(l <= r)
{
if (a[mid] < x){
l = mid+;
mid = (l+r) / ;
}
else if (a[mid] > x)
{
r = mid-;
mid = (l+r)/;
}
else return true;
}
return false; }
int main()
{
freopen("in.txt", "r", stdin);
int m, ans = ;
while(~scanf("%d%d", &n, &m))
{
ans = ;
if ( m== && n == ) break;
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
int tmp;
for (int i = ; i < m; i++)
{
scanf("%d", &tmp);
if (search(tmp))
ans++;
}
printf("%d\n", ans);
}
return ;
}

最新文章

  1. java面试知识(来自牛客网)
  2. SQL Server 2008 R2——查找最小nIndex,nIndex存在而nIndex+1不存在 求最小连续数组中的最大值
  3. 初识Linux—1
  4. datagrid---写后台数据交互
  5. 【Android UI设计与开发】第05期:引导界面(五)实现应用程序只启动一次引导界面
  6. ruby self.included用法
  7. Global::validateEmail
  8. 高级停靠(Dock)技术的实现
  9. 记一次dedeCMS网站搭建全过程
  10. 动手编写插件-javascript分页插件
  11. over 分析函数之 lag() lead()
  12. Linux tomcat部署War包,Linux在Tomcat部署JavaWeb项目,Linux部署War包
  13. HttpServletResponse对象介绍
  14. DMA设计
  15. 一个关于cookie的坑
  16. Android开发 ---Fragment片段布局
  17. 【BZOJ】【1178】【APIO2009】convention会议中心
  18. Cloudstack 安装记录
  19. Extjs MVC模式
  20. 选择IM云服务供应商

热门文章

  1. 迭代器———更锋利的C#代码小记(3)
  2. springmvc、springboot静态资源访问配置
  3. HTTPS时代已来,你做好准备了吗?
  4. 设置QtreeWidget水平滚动条
  5. Angular JS中变量定义的基本原则
  6. 为什么ABAP整型的1转成string之后,后面会多个空格
  7. windows安装tensorflow的一个教训
  8. docker之启动创建容器流程
  9. [bzoj4899]记忆的轮廓 题解(毒瘤概率dp)
  10. ImportError: pycurl: libcurl link-time ssl backend (nss) is different