[数据结构与算法]Dot Product of Two Sparse Vectors

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

思路：就是用hashmap收集非0的index和value，然后loop keyset小的vec，找到相对应的index乘积积累起来就是答案；

class SparseVector {
    private HashMap<Integer, Integer> hashmap;
    SparseVector(int[] nums) {
        this.hashmap = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != 0) {
                hashmap.put(i, nums[i]);
            }
        }
    }
    
	// Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        if(vec.hashmap.size() < this.hashmap.size()) {
            return vec.dotProduct(this);
        }
        int res = 0;
        for(Integer curKey: this.hashmap.keySet()) {
            if(vec.hashmap.containsKey(curKey)) {
                res += hashmap.get(curKey) * vec.hashmap.get(curKey);
            }
        }
        return res;
    }
}

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

?

阅读世界，共赴山海

423全民读书节，邀你共读