向量Python实现100分"/>
CSP-稀疏向量Python实现100分
思路:用俩个字典分别记录俩个向量的非零值的位置以及对应的值,将位置作为key,对应的值作为value,因为位置肯定不会重复的,然后计算的时候遍历非零值较少的那个向量(可以通过比较a和b的大小得出),这样做可以降低一点时间复杂的,因为求向量内积必须是俩个向量中相同位置的值都不为0才需要计算,其他情况都为0。
测试数据:
测试数据
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40
代码:
n,a,b = map(int,input().split())
# 将俩个向量的非0部分的位置和值分别放入字典中,以位置作为key
map_a = {}
map_b = {}
for _ in range(a):ind,val = map(int,input().split())map_a[ind] = val
for _ in range(b):ind,val = map(int,input().split())map_b[ind] = val
# 保存结果
result = 0
# 在长度的小的字典中进行遍历,可以省一点时间
if a<b:# 遍历字典的语法for key,value in map_a.items():# 看在b向量中这个位置的值为0吗,不为0才需要计算if key in map_b:result += value*map_b[key]
else:# 遍历字典的语法for key,value in map_b.items():if key in map_a:result += value*map_a[key]
print(result)
更多推荐
CSP-稀疏向量Python实现100分
发布评论