LeetCode 1570. 兩個稀疏向量的點積(哈希)

Michael阿明 2021-08-15 22:28:37 阅读数:264

本文一共[544]字,预计阅读时长:1分钟~
leetcode 稀疏 向量 哈希

文章目錄

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_map<int,int> m;
int size = 0;
SparseVector(vector<int> &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 vectors
int 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阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753191x.html