← 返回 meta 的题目列表Sparse Vector Dot Product
类型：online_judge
Given two sparse vectors v1 and v2 of equal length n (where n can be very large but the number of non-zero entries is small), design a data structure and implement an efficient method to compute their dot product.
Requirements:
Choose a representation that makes dot product computation efficient.
Discuss time and space complexity.
Example:
Input: v1 = [1,0,0,2,3], v2 = [0,3,0,4,0]
Output: 8
Constraints:
1 <= n <= 1e7
Non-zero count is much smaller than n
Example
Input
v1=[1,0,0,2,3]
v2=[0,3,0,4,0]
Output
8