• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

Linear Search

AOJ 站点默认 8个月前 (04-09) 266次浏览 已收录 1个评论
文章目录[隐藏]

Question

You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.

Input
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.

Output
Print C in a line.

Constraints
n ≤ 10000
q ≤ 500
0 ≤ an element in S ≤ 109
0 ≤ an element in T ≤ 109
Sample Input 1
5
1 2 3 4 5
3
3 4 1
Sample Output 1
3
Sample Input 2
3
3 1 2
1
5
Sample Output 2
0
Sample Input 3
5
1 1 2 2 3
2
1 2
Sample Output 3
2
Notes

Meaning

题目很简单,但是这里主要讲一个:线性搜索在引入标记之后,效率能提升常数倍。

Coding

Summary


向线性搜索种引入“标记”能够以将算法效率提升常数倍。
原始:

改进后,给要查找的数放在数组末尾,用作标记。


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Linear Search
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(1)个小伙伴在吐槽
  1. it's tricky to tighten its back plate.
    匿名2020-11-21 22:28 回复 Windows 10 | Chrome 62.0.3202.94