KK's blog

每天积累多一些

0%

LeetCode 1570 Dot Product of Two Sparse Vectors

Posted on Disqus:

LeetCode



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?

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) = 10 + 03 + 00 + 24 + 30 = 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) = 00 + 10 + 00 + 00 + 02 = 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.length 1 <= n <= 10^5
* 0 <= nums1[i], nums2[i] <= 100

题目大意：

稀疏数组乘法，设计类来存储且计算乘积

HashMap解题思路：

类似于Two sum，也是两种方法。HashMap的方法由于hash函数计算容易冲突，所以算法复杂度不够稳定。

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SparseVector(TestCases):

    def __init__(self, nums: List[int]):
        self.idx_to_num = collections.defaultdict(int)
        for i, n in enumerate(nums):
            if n > 0:
                self.idx_to_num[i] = n

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        res = 0
        for i, n in vec.idx_to_num.items():
            if i in self.idx_to_num:
                res += self.idx_to_num[i] * n
        return res

算法分析：

创建时间复杂度为O(n)，计算时间复杂度为O(L)，空间复杂度O(L)，L为非0元素个数

Mergesort算法II解题思路：

初始化复杂度比较稳定

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class SparseVector(TestCases):

    def __init__(self, nums: List[int]):
        self.non_zero_list = []
        for i, n in enumerate(nums):
            if n > 0:
                self.non_zero_list.append((i,n))

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        i, j, res = 0, 0, 0
        while i <= len(self.non_zero_list) - 1 and j <= len(vec.non_zero_list) - 1:
            if self.non_zero_list[i][0] == vec.non_zero_list[j][0]:
                res += self.non_zero_list[i][1] * vec.non_zero_list[j][1]
                i += 1
                j += 1
            elif self.non_zero_list[i][0] < vec.non_zero_list[j][0]:
                i += 1
            else:
                j += 1
        return res

算法分析：

创建时间复杂度为O(n)，计算时间复杂度为O(L1 + L2)，空间复杂度O(L)，L为非0元素个数

Free mock interview