1570. 两个稀疏向量的点积
给定两个稀疏向量，计算它们的点积（数量积）。
实现类 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.length1 <= n <= 10^50 <= nums1[i], nums2[i] <= 100原站题解
golang 解法, 执行用时: 172 ms, 内存消耗: 8 MB, 提交时间: 2023-10-16 21:00:09
type SparseVector struct {
DataMap map[int]int
}
func Constructor(nums []int) SparseVector {
dataMap := make(map[int]int)
for i := 0; i < len(nums); i++ {
if nums[i] != 0 {
dataMap[i] = nums[i]
}
}
return SparseVector{
DataMap: dataMap,
}
}
// Return the dotProduct of two sparse vectors
func (this *SparseVector) dotProduct(vec SparseVector) int {
sum := 0
for k, v := range this.DataMap {
if v2, ok := vec.DataMap[k]; ok {
sum += v * v2
}
}
return sum
}
/**
* Your SparseVector object will be instantiated and called as such:
* v1 := Constructor(nums1);
* v2 := Constructor(nums2);
* ans := v1.dotProduct(v2);
*/
rust 解法, 执行用时: 20 ms, 内存消耗: 3.2 MB, 提交时间: 2023-10-16 20:59:45
struct SparseVector {
v : Vec<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl SparseVector {
fn new(nums: Vec<i32>) -> Self {
SparseVector { v : nums, }
}
// Return the dotProduct of two sparse vectors
fn dot_product(&self, vec: SparseVector) -> i32 {
let mut sum = 0;
for i in 0..self.v.len() {
sum += self.v[i] * vec.v[i];
}
sum
}
}
/**
* Your SparseVector object will be instantiated and called as such:
* let v1 = SparseVector::new(nums1);
* let v2 = SparseVector::new(nums2);
* let ans = v1.dot_product(v2);
*/
java 解法, 执行用时: 10 ms, 内存消耗: 53.9 MB, 提交时间: 2023-10-16 20:59:17
class SparseVector1 {
List<int[]> list;
SparseVector1(int[] nums) {
this.list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
this.list.add(new int[]{i, nums[i]});
}
}
}
// Return the dotProduct of two sparse vectors
public int dotProduct(SparseVector1 vec) {
int index1 = 0, index2 = 0;
int product = 0;
while (index1 < this.list.size() && index2 < vec.list.size()) {
if (this.list.get(index1)[0] == vec.list.get(index2)[0]) {
product += this.list.get(index1)[1] * vec.list.get(index2)[1];
index1++;
index2++;
} else if (this.list.get(index1)[0] < vec.list.get(index2)[0]) {
index1++;
} else {
index2++;
}
}
return product;
}
}
class SparseVector {
Map<Integer, Integer> map;
SparseVector(int[] nums) {
map = new HashMap<>();
for(int i=0; i<nums.length; i++){
if(nums[i]!=0) map.put(i, nums[i]);
}
}
// Return the dotProduct of two sparse vectors
public int dotProduct(SparseVector vec) {
int res = 0;
if(this.map.size()<vec.map.size()){
for(int i:this.map.keySet()){
if(vec.map.containsKey(i)) res += this.map.get(i)*vec.map.get(i);
}
}else{
for(int i:vec.map.keySet()){
if(this.map.containsKey(i)) res += this.map.get(i)*vec.map.get(i);
}
}
return res;
}
}
// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.dotProduct(v2);
python3 解法, 执行用时: 1472 ms, 内存消耗: 20.1 MB, 提交时间: 2023-10-16 20:58:58
class SparseVector:
def __init__(self, nums: List[int]):
self.sparse_idx = []
self.sparse_val = []
for i, val in enumerate(nums):
if val != 0:
self.sparse_idx.append(i)
self.sparse_val.append(val)
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int:
ptr_one = 0
ptr_two = 0
out = 0
while ptr_one < len(self.sparse_idx) and ptr_two < len(vec.sparse_idx):
if self.sparse_idx[ptr_one] == vec.sparse_idx[ptr_two]:
out += (self.sparse_val[ptr_one] * vec.sparse_val[ptr_two])
ptr_one += 1
ptr_two += 1
elif self.sparse_idx[ptr_one] < vec.sparse_idx[ptr_two]:
ptr_one += 1
else:
ptr_two += 1
return out
# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)
cpp 解法, 执行用时: 176 ms, 内存消耗: 166.5 MB, 提交时间: 2023-10-16 20:56:41
class SparseVector1 {
public:
SparseVector1(vector<int> &nums) {
this->nums = nums;
}
// Return the dotProduct of two sparse vectors
int dotProduct(SparseVector1& vec) {
assert(nums.size() == vec.size() && !nums.empty());
int productSum = 0;
for (int i = 0; i < vec.size(); i++) {
productSum += vec.getNum(i) * nums[i];
}
return productSum;
}
int getNum(int i) {
assert(i < nums.size());
return nums[i];
}
int size() {
return nums.size();
}
private:
vector<int> nums;
};
class SparseVector2 {
public:
unordered_map<int, int> mp; // map from index to value for non zero value
SparseVector2(vector<int> &nums) {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
mp[i] = nums[i];
}
}
}
// Return the dotProduct of two sparse vectors
int dotProduct(SparseVector2& vec) {
int productSum = 0;
for (const auto& m : vec.mp) {
auto& [index, value] = m;
productSum += value * mp[index];
}
return productSum;
}
};
class SparseVector {
public:
unordered_map<int, int> mp; // map from index to value for non zero value
SparseVector(vector<int> &nums) {
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
mp[i] = nums[i];
}
}
}
// Return the dotProduct of two sparse vectors
int dotProduct(SparseVector& vec) {
int productSum = 0;
auto& sparserVecMap = mp.size() < vec.mp.size() ? mp : vec.mp;
auto& DenserVecMap = mp.size() < vec.mp.size() ? vec.mp : mp;
for (const auto& m : sparserVecMap) {
auto& [index, value] = m;
productSum += value * DenserVecMap[index];
}
return productSum;
}
};
// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);