Leetcode - 1570. Dot Product of Two Sparse Vectors

문제

두 sparse vector(대부분 값이 0인)를 dot product연산한 결과를 출력해라. 두 벡터는 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

해결 아이디어

• hashtable
  대부분의 값이 0이기 때문에 <인덱스, 값> 해시테이블에 값이 0이 아닌 요소만 넣는다. 그 뒤 테이블을 순회하며 둘다 0이 아닌 값만 곱해서 더한다.

• two pointer
  0이 아닌 값만 pair<인덱스, 값> 를 vector에 저장. 그 뒤 two pointer를 각각 증가시키며 두 인덱스가 같을때만 dot product연산. 이 해결방식을 잘 기억하기.

해결 hashtable

class SparseVector {
public:
    unordered_map<int, int> v;
    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                v[i] = nums[i];    
            }
        }
    }
    
    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int dp = 0;
        for (auto it: vec.v) {
            if (it.second != 0 && v[it.first] != 0) {
                dp += it.second * v[it.first];
            }
        }
        return dp;
    }
};

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

해결 two pointer

class SparseVector {
public:
    vector<pair<int, int>> v;
    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                v.push_back(make_pair(i, nums[i]));    
            }
        }
    }
    
    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int dp = 0;
        int p = 0, q = 0;
        while (p < v.size() && q < vec.v.size()) {
            if (v[p].first == vec.v[q].first) {
                dp += v[p].second * vec.v[q].second;
                p++;
                q++;
            } else if (v[p].first > vec.v[q].first) {
                q++;
            } else {
                p++;
            }
        }
        return dp;
    }
};