两个稀疏向量的点积

Submission

运行时间: 1188 ms

内存: 21.6 MB

class SparseVector0:
    def __init__(self, nums: List[int]):
        self.pair = []
        for i, num in enumerate(nums):
            if num != 0:
                self.pair.append([i, num])
        

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





class SparseVector:
    def __init__(self, nums: List[int]):
        self.dic = defaultdict(int)
        for i, num in enumerate(nums):
            if num != 0:
                self.dic[i] = num 
        

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

# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)

Explain

题解中包括两种方法来实现稀疏向量的点积。第一种方法是使用列表来存储非零元素的索引和值，第二种方法使用字典来存储非零元素的索引和值。在第一种方法中，通过双指针技术在两个向量的非零元素索引中进行遍历，当两个索引相等时计算乘积并累加到结果中。在第二种方法中，遍历一个向量的所有非零元素索引，检查这些索引是否在另一个向量中也是非零的，如果是，则计算乘积并累加到结果中。这两种方法都有效地利用了稀疏向量中大量零元素的特性，从而优化了计算点积的过程。

时间复杂度: O(k)

空间复杂度: O(k)


class SparseVector0:
    def __init__(self, nums: List[int]):
        # Initialize storage for non-zero elements
        self.pair = []
        for i, num in enumerate(nums):
            if num != 0:
                self.pair.append([i, num])

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        # Initialize result
        res = 0
        # Two pointers for each vector's non-zero elements
        si, vi = 0, 0
        while si < len(self.pair) and vi < len(vec.pair):
            if self.pair[si][0] == vec.pair[vi][0]:
                # Multiply and accumulate when indices match
                res += self.pair[si][1] * vec.pair[vi][1]
                si += 1
                vi += 1
            elif self.pair[si][0] > vec.pair[vi][0]:
                vi += 1
            else:
                si += 1
        return res



class SparseVector:
    def __init__(self, nums: List[int]):
        # Use dictionary to store non-zero elements
        self.dic = defaultdict(int)
        for i, num in enumerate(nums):
            if num != 0:
                self.dic[i] = num 

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        # Initialize result
        res = 0
        # Iterate over non-zero elements
        for i in self.dic.keys():
            if i in vec.dic:
                # Multiply and accumulate when indices match
                res += self.dic[i] * vec.dic[i]
        return res

# Usage example is omitted but involves creating instances and calling dotProduct method

Explore

在实现稀疏向量点积时，使用列表和字典两种数据结构主要是为了利用各自的数据结构特性来优化性能。列表方法中，通过存储索引和值的对，可以在遍历时通过双指针技术有效地查找和计算匹配索引的值。这种方法的优点是在两个向量都较为稀疏且索引分布均匀时，能够高效地进行匹配和计算。缺点是需要手动管理索引位置，且在两个向量非零元素数量差异较大时效率可能会降低。字典方法通过键值对直接存储索引和值，查找效率高，适合非零元素索引随机分布的情况，特别是当一个向量非常稀疏而另一个相对密集时。但是，这种方法可能在内存使用上不如列表方法经济，特别是在非零元素极少的情况下。

在使用双指针技术进行点积计算时，两个指针分别指向两个向量的非零元素。指针移动的条件是比较两个非零元素的索引：如果两个索引相等，则计算乘积并将两个指针同时向前移动；如果不相等，则移动较小索引的指针以便尽快找到下一个可能的匹配。这种移动方式是因为，只有当两个索引相等时，才能贡献到点积的结果中，移动较小的索引可以快速跳过那些无法匹配的索引，从而提高遍历的效率。

在极端稀疏的情况下，即向量中非零元素极少时，两种方法的性能表现各有千秋。列表方法的性能主要受到两个向量中非零元素数量的影响，如果两个向量的非零元素数量相对均衡且都很少，那么双指针遍历的效率很高，因为它可以快速跳过大量的零。字典方法在这种情况下也表现良好，尤其是当其中一个向量非常稀疏而另一个非零元素稍多时，因为只需遍历非零元素更少的向量的索引，并检查这些索引在另一向量中是否也是非零的。总的来说，字典方法在处理非常不均匀的稀疏向量时可能稍优一些，因为其查找操作是常数时间的，而列表方法在非零元素分布相对均匀时效率更高。