LC 1570 [M] Dot Product of Two Sparse Vectors - ALawliet/algorithms GitHub Wiki
intuitive? Y
instantiate the SparseVectors with maps of index => non-zero number and only compute those indexes
gotcha:
- using a map lets you lookup values without having to store the list of nums
optimal
class SparseVector:
def __init__(self, nums: List[int]):
self.nonzeros_i_to_x = {}
for i, x in enumerate(nums):
if x != 0:
self.nonzeros_i_to_x[i] = x
def dotProduct(self, other: 'SparseVector') -> int:
res = 0
# iterate through each non-zero element in this sparse vector
# update the dot product if the corresponding index has a non-zero value in the other vector
for i, x in self.nonzeros_i_to_x.items():
if i in other.nonzeros_i_to_x:
res += (x * other.nonzeros[i])
return res
class SparseVector:
def __init__(self, nums: List[int]):
self.nums = nums # just so we can use later
self.nonzero_indexes = set()
for i, x in enumerate(nums):
if x != 0:
self.nonzero_indexes.add(i)
# print(self.nonzero_indexes)
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int: # other
dot = 0
for i in self.nonzero_indexes:
for j in vec.nonzero_indexes:
if i == j:
dot += (self.nums[i] * vec.nums[j])
return dot
set() intersection more intuitive but a little slower
class SparseVector:
def __init__(self, nums: List[int]):
self.nonzero = set()
for i in range(len(nums)):
if nums[i] != 0:
self.nonzero.add(i)
print(self.nonzero)
self.nums = nums
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int:
product = 0
both_nonzero = self.nonzero.intersection(vec.nonzero)
for i in both_nonzero:
product += (self.nums[i] * vec.nums[i])
return product
just no...
class SparseVector:
def __init__(self, A: List[int]):
self.m = {i: x for i, x in enumerate(A) if x}
def dotProduct(self, other: 'SparseVector') -> int:
return sum([x * y for i, x in self.m.items() for j, y in other.m.items() if i == j])