【Leetcode】1570. Dot Product of Two Sparse Vectors

题目地址：

https://leetcode.com/problems/dot-product-of-two-sparse-vectors/description/

要求设计一个稀疏向量的类，实现：
1、初始化。给定一个数组，用其初始化这个稀疏向量，要求用的存储空间尽量小。
2、和另一个稀疏向量做内积。

用一个哈希表存，只存非零的项，key为下标，val为值。做内积的时候也只看非零项。代码如下：

class SparseVector {
 public:
  unordered_map<int, int> v;

  SparseVector(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++)
      if (nums[i]) v[i] = nums[i];
  }

  // Return the dotProduct of two sparse vectors
  int dotProduct(SparseVector& vec) {
    auto v2 = vec.v;
    int res = 0;
    for (auto& [k, n] : v)
      if (v2.count(k)) res += n * v2[k];

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时空复杂度$O(n_0)$，$n_0$为非零数的个数。