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

Linear Search

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

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)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到
(24)个小伙伴在吐槽
  1. payday loan online http://quicken4loans.com loan online
    匿名2021-05-17 23:59 (19小时前)回复 Windows 7 | Chrome 83.0.4093.3
  2. albuterol rx https://albuterolotc.com/ how much is albuterol sulfate
    匿名2021-05-17 18:08 (1天前)回复 Windows 10 | Chrome 83.0.4103.44
  3. proventil albuterol https://ventolinhfaer.com side effects of albuterol inhaler
    匿名2021-05-17 13:47 (1天前)回复 Windows 7 | Chrome 83.0.4103.61
  4. buy cialis with paypal ordering cialis online australia - buy cialis tadalafil0 with pay pal generic cialis 20 mg tadalafil
    匿名2021-05-17 04:06 (2天前)回复 Windows 10 | Chrome 83.0.4103.61
  5. vardenafil hcl 20mg tab http://levitrair.com vardenafil hcl 20mg tab
    匿名2021-05-16 20:43 (2天前)回复 Windows 10 | Chrome 83.0.4100.3
  6. cialis original for sale buy cialis cheap canada - buy cialis insurancecialis online without prescription generic cialis daily pricing
    匿名2021-05-16 05:50 (3天前)回复 Windows 10 | Chrome 83.0.4089.0
  7. ivermectin tablets http://ivermectineffects.com ivermectin tablets for humans
    匿名2021-05-15 18:11 (3天前)回复 Windows 10 | Chrome 83.0.4086.0
  8. buy cialis online viagra cialis 5mg tablet - cialis for daily use cialis without presciption in usa
    匿名2021-05-14 09:16 (4天前)回复 Windows 8.1 | Chrome 83.0.4103.61
  9. azithromycin pack http://zithrozpack.com/ how long for azithromycin to take effect
    匿名2021-05-14 02:58 (5天前)回复 Windows 10 | Chrome 83.0.4103.61
  10. http://ivermectinus.com/ ivermectin for humans dosage
    匿名2021-05-13 10:39 (5天前)回复 Windows 10 | Chrome 83.0.4103.61
  11. ivermectin over the counter http://ivermectinovercounter.com/# reddit canadian pharmacy
    匿名2021-05-13 06:57 (6天前)回复 Windows 10 | Chrome 83.0.4086.0
  12. canadian pharmacies mail order
    匿名2021-05-13 02:58 (6天前)回复 Windows 10 | Chrome 67.0.3396.62
  13. cialis vs viagra order viagra online - viagra online buy viagra order
    匿名2021-05-12 23:28 (6天前)回复 Windows 10 | Chrome 83.0.4103.0
  14. viagra online 100mg viagra without a doctor prescription - viagra without doctor prescription viagra side effects
    匿名2021-05-12 01:40 (7天前)回复 Windows 10 | Chrome 83.0.4093.3
  15. online pharmacy canada
    匿名2021-05-12 00:07 (7天前)回复 Windows 10 | Chrome 48.0.2564.116
  16. best canadian online pharmacy
    匿名2021-05-11 23:22 (7天前)回复 Windows 10 | Chrome 63.0.3239.26
  17. canada drugs
    匿名2021-05-11 22:02 (7天前)回复 Windows 10 | Chrome 63.0.3239.26
  18. viagra without a doctor prescription viagra without doctor prescription - free viagra viagra without prescription
    匿名2021-05-10 21:57 回复 Windows 10 | Chrome 83.0.4087.0
  19. canadian pharmacies online
    匿名2021-05-10 19:36 回复 Windows XP | 搜狗浏览器 2.X
  20. ivermectin over the counter http://ivermectinovercounter.com/ ivermectin
    匿名2021-05-10 03:13 回复 Windows 7 | Chrome 83.0.4103.61
  21. http://www.withoutbro.com viagra prescription online
    匿名2021-05-09 13:56 回复 Windows 7 | Chrome 83.0.4103.61
  22. ivermectine sans ordonnance https://iwermectin.com/ ivermectin side effects
    匿名2021-05-09 06:04 回复 Windows 10 | Chrome 83.0.4103.61
  23. ivermectin for humans for sale http://ivermectineffects.com/# ivermectin otc
    匿名2021-05-08 18:55 回复 Windows 7 | Chrome 83.0.4103.61