Description
Given two sparse vectors, compute their dot product.
Implement class SparseVector:
SparseVector(nums) Initializes the object with the vector numsdotProduct(vec) Compute the dot product between the instance of SparseVector and vec
A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.
Follow up: What if only one of the vectors is sparse?
Example 1:
Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8
Example 2:
Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0
Example 3:
Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6
Constraints:
n == nums1.length == nums2.length1 <= n <= 10^50 <= nums1[i], nums2[i] <= 100
Solutions
Solution 1: Hash Map
We use a hash map d to store non-zero elements, where the key is the index, and the value is the corresponding value. We iterate through nums, and if nums[i] is not 0, we add (i, nums[i]) to the hash map d.
When calculating the dot product, we iterate through the hash map with fewer non-zero elements and check if the other hash map contains the corresponding key. If it exists, we multiply the corresponding values and add them to the result.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
PythonJavaC++GoTypeScriptRust
class SparseVector:
def __init__(self, nums: List[int]):
self.d = {i: v for i, v in enumerate(nums) if v}
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: "SparseVector") -> int:
a, b = self.d, vec.d
if len(b) < len(a):
a, b = b, a
return sum(v * b.get(i, 0) for i, v in a.items())
# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)(code-box)
class SparseVector {
public Map<Integer, Integer> d = new HashMap<>(128);
SparseVector(int[] nums) {
for (int i = 0; i < nums.length; ++i) {
if (nums[i] != 0) {
d.put(i, nums[i]);
}
}
}
// Return the dotProduct of two sparse vectors
public int dotProduct(SparseVector vec) {
var a = d;
var b = vec.d;
if (b.size() < a.size()) {
var t = a;
a = b;
b = t;
}
int ans = 0;
for (var e : a.entrySet()) {
int i = e.getKey(), v = e.getValue();
ans += v * b.getOrDefault(i, 0);
}
return ans;
}
}
// 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);(code-box)
class SparseVector {
public:
unordered_map<int, int> d;
SparseVector(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
if (nums[i]) {
d[i] = nums[i];
}
}
}
// Return the dotProduct of two sparse vectors
int dotProduct(SparseVector& vec) {
auto a = d;
auto b = vec.d;
if (a.size() > b.size()) {
swap(a, b);
}
int ans = 0;
for (auto& [i, v] : a) {
if (b.count(i)) {
ans += v * b[i];
}
}
return ans;
}
};
// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);(code-box)
type SparseVector struct {
d map[int]int
}
func Constructor(nums []int) SparseVector {
d := map[int]int{}
for i, x := range nums {
if x != 0 {
d[i] = x
}
}
return SparseVector{d}
}
// Return the dotProduct of two sparse vectors
func (this *SparseVector) dotProduct(vec SparseVector) (ans int) {
a, b := this.d, vec.d
if len(a) > len(b) {
a, b = b, a
}
for i, x := range a {
if y, has := b[i]; has {
ans += x * y
}
}
return
}
/**
* Your SparseVector object will be instantiated and called as such:
* v1 := Constructor(nums1);
* v2 := Constructor(nums2);
* ans := v1.dotProduct(v2);
*/(code-box)
class SparseVector {
d: Map<number, number>;
constructor(nums: number[]) {
this.d = new Map();
for (let i = 0; i < nums.length; ++i) {
if (nums[i] != 0) {
this.d.set(i, nums[i]);
}
}
}
// Return the dotProduct of two sparse vectors
dotProduct(vec: SparseVector): number {
let a = this.d;
let b = vec.d;
if (a.size > b.size) {
[a, b] = [b, a];
}
let ans = 0;
for (const [i, x] of a) {
if (b.has(i)) {
ans += x * b.get(i)!;
}
}
return ans;
}
}
/**
* Your SparseVector object will be instantiated and called as such:
* var v1 = new SparseVector(nums1)
* var v2 = new SparseVector(nums1)
* var ans = v1.dotProduct(v2)
*/(code-box)
use std::collections::HashMap;
#[derive(Clone)]
struct SparseVector {
d: HashMap<usize, i32>,
}
impl SparseVector {
fn new(nums: Vec<i32>) -> Self {
let mut d = HashMap::new();
for (i, &x) in nums.iter().enumerate() {
if x != 0 {
d.insert(i, x);
}
}
SparseVector { d }
}
fn dot_product(&self, vec: SparseVector) -> i32 {
let (a, b) = (&self.d, &vec.d);
let mut ans = 0;
if a.len() > b.len() {
return vec.dot_product(self.clone());
}
for (&i, &x) in a.iter() {
if let Some(&y) = b.get(&i) {
ans += x * y;
}
}
ans
}
}(code-box)
