注册 登录
编程论坛 数据结构与算法

用线性表解决,这个问题!

jj369258 发布于 2011-09-27 23:34, 997 次点击
Description
一只笨小猴A有香蕉、苹果、葡萄、西瓜等几种水果,另一只笨小猴B有桔子、香蕉、西红柿、葡萄、红枣等几种水果,写一算法,得到两只小猴一共有的水果种类。约定用不同的整数代表不同的水果。
Input
第1行为一个整数t(1≤t≤10),表示接下来有t 个测试数据。 然后输入小猴A的水果种类,小猴A种数的整数表示;输入小猴B的水果种类,小猴B种数的整数表示。
Output
小猴A和B共有的水果种类数。
Sample Input
2
7
1 3 7 9 4 8 12
9
1 2 5 7 3 4 12 8 11
5
2 3 6 11 9
8
3 5 7 10 2 11 6 24
Sample Output
10
9
2 回复
#2
beyondyf2011-09-28 00:07
你是为了解题还是为了练习使用线性表?
解这题用不着线性表,而且用线性表的效率更差。
用线性表的时间复杂度是O(A * B),用数组可以达到O(log(A) * B)。
如果可以知道表示水果种类的整数的上限,可以做到O(A + B).
#3
jj3692582011-09-29 10:01
回复 2楼 beyondyf
不会做啊 !头痛,要用线性表解决,用数组可能还简单一些,是把?
1