黄页网站推广app,yellow网站推广联盟,山东新闻 最新消息 今天,网站优化收费文章目录1. 题目2. 解题1. 题目
给定两个稀疏向量#xff0c;计算它们的点积#xff08;数量积#xff09;。
实现类 SparseVector#xff1a;
SparseVector(nums) 以向量 nums 初始化对象。dotProduct(vec) 计算此向量与 vec 的点积。
稀疏向量 是指绝大多数分量为 0 …
文章目录1. 题目2. 解题1. 题目
给定两个稀疏向量计算它们的点积数量积。
实现类 SparseVector
SparseVector(nums) 以向量 nums 初始化对象。dotProduct(vec) 计算此向量与 vec 的点积。
稀疏向量 是指绝大多数分量为 0 的向量。 你需要 高效 地存储这个向量并计算两个稀疏向量的点积。
进阶当其中只有一个向量是稀疏向量时你该如何解决此问题
示例 1
输入nums1 [1,0,0,2,3], nums2 [0,3,0,4,0]
输出8
解释v1 SparseVector(nums1) , v2 SparseVector(nums2)
v1.dotProduct(v2) 1*0 0*3 0*0 2*4 3*0 8示例 2
输入nums1 [0,1,0,0,0], nums2 [0,0,0,0,2]
输出0
解释v1 SparseVector(nums1) , v2 SparseVector(nums2)
v1.dotProduct(v2) 0*0 1*0 0*0 0*0 0*2 0示例 3
输入nums1 [0,1,0,0,2,0,0], nums2 [1,0,0,0,3,0,4]
输出6提示
n nums1.length nums2.length
1 n 10^5
0 nums1[i], nums2[i] 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/dot-product-of-two-sparse-vectors 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
使用 哈希 存储非0的元素key 是下标value 是值
class SparseVector {
public:unordered_mapint,int m;int size 0;SparseVector(vectorint nums) {size nums.size();for(int i 0; i nums.size(); i){if(nums[i])m[i] nums[i];}}// Return the dotProduct of two sparse vectorsint dotProduct(SparseVector vec) {int ans 0;for(auto kv : vec.m){if(m.find(kv.first) ! m.end()){ans m[kv.first]*kv.second;}}return ans;}
};// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans v1.dotProduct(v2);184 ms 164.6 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步