题目描述
Given two sparse vectors, compute their dot product.
Implement class SparseVector:
- SparseVector(nums) Initializes the object with the vector nums
- dotProduct(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?
样例
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
算法1 (Index-Value Pairs模拟)
时间复杂度: O(n) for creating non-zero index-value pairs, O(l1+l2) for dot product
空间复杂度: O(l1) and O(1)
C++ 代码
typedef pair<int, int> PII;
class SparseVector {
public:
vector<PII> v;
SparseVector(vector<int> &nums) {
for (int i = 0; i < nums.size(); i++)
if (nums[i])
v.push_back({i, nums[i]});
}
// Return the dotProduct of two sparse vectors
int dotProduct(SparseVector& vec) {
int res = 0;
for (int i = 0, j = 0; i < v.size() && j < vec.v.size(); i++, j++) {
if (v[i].first < vec.v[j].first) j--;
else if (v[i].first > vec.v[j].first) i--;
else res += v[i].second * vec.v[j].second;
}
return res;
}
};
// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);
算法2 (Index-Value Pairs, 二分)
For the follow-up question, if the length of one sparse vector’s non-zero element is much greater than the other one’s, we could use binary search on the long sparse vector.
时间复杂度: O(min(l1,l2)∗log(max(l1,l2)))
空间复杂度: 同上
C++ 代码
typedef pair<int, int> PII;
class SparseVector {
public:
vector<PII> v;
SparseVector(vector<int> &nums) {
for (int i = 0; i < nums.size(); i++)
if (nums[i])
v.push_back({i, nums[i]});
}
// Return the dotProduct of two sparse vectors
int dotProduct(SparseVector& vec) {
int res = 0;
vector<PII>& v_short = vec.v;
vector<PII>& v_long = v;
if (v_short.size() > v_long.size())
swap(v_short, v_long);
for (auto &p: v_short) {
int idx = lower_bound(v_long.begin(), v_long.end(), make_pair(p.first, - 1)) - v_long.begin();
if (idx != v_long.size() && v_long[idx].first == p.first)
res += v_long[idx].second * p.second;
}
return res;
}
};
// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);