05 August 2008
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class SparseVector {
Map<Integer, Integer> map; // For all non-zero values in the vector, we map the index to the non-zero value.
// O(nums.length) time.
// O(numNonZeroValues) space.
SparseVector(int[] nums) {
map = new HashMap<>();
// Store the position and value of non-zero values.
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
map.put(i, nums[i]);
}
}
}
// Return the dotProduct of two sparse vectors
// O(min(vec1numNonZeroValues, vec2numNonZeroValues)) time because we iterate through non-zero values of the vector that has fewer non-zero values and for each value we check in O(1) time whether the other vector has a non-zero value at that index.
// O(1) space.
public int dotProduct(SparseVector vec) {
if (vec.map.size() < this.map.size()) {
return vec.dotProduct(this); // We want to iterate through the smaller map.
}
int result = 0;
for (Integer currIdx : this.map.keySet()) {
// If both vectors have a non-zero value at currIdx then multiply the values and add them to the result.
if (vec.map.containsKey(currIdx)) {
result += this.map.get(currIdx) * vec.map.get(currIdx);
}
}
return result;
}
}
// 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);