[LeetCode] 1570. Dot Product of Two Sparse Vectors

1570. Dot Product of Two Sparse Vectors

Medium

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) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 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) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 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

---

문제 풀이

문제 접근

1. n 은 각 리스트의 길이다.
2. n 은 최대 10^5 이기 때문에, N 시간 복잡도 안에 풀려야한다. 
3. 알고리즘이 필요없어 보이고, 탐색을 한번 즉 for 하나로 풀 수 있을 것 같다. 
4. 속도를 개선하려면 Hash table 을 사용한다.

풀이

1. 클래스에서 각 리스트를 초기화 해줘야 하는데, 이때 값이 0 인 곳은 계산 하지 않아도 된다.
2. 0 이 아닌 것을 탐색할 자료에서 배제 시키려면 딕셔너리 (해쉬 테이블) 을 사용한다, 하지만 리스트 두개를 동시에 탐색해도 풀린다. 
3. 딕셔너리에 키 값은 인덱스로 값 부분은 곱할 숫자를 넣는다. 
4. 다음 dotProduct 함수에서 클래스 초기화 때 만들어 놓은 딕셔너리를 활용한다.
5. 그 딕셔너리에서 0 이 아닌 숫자들만 현재 클래스의 딕셔너리에서 불러와서 답을 구한다. 

소스 코드

class SparseVector:
    def __init__(self, nums: List[int]):
        self.hashmap = dict()
        for index, value in enumerate(nums):
            if value > 0: 
                self.hashmap[index] = value

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

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