dot product 1570

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

解法一：直截了当，对应位置相乘，得到结果. 但是对于稀疏向量并且多次重复调用的话 不是非常efficient.

时间复杂度： O(N)

空间复杂度：O(1)

class SparseVector {
    int[] nums;
    SparseVector(int[] nums) {
        this.nums = nums;
    }
    
    // Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int sum=0;
        for(int i=0;i){
            sum+=nums[i]*vec.nums[i];
        }
        return sum;
    }
}

解法二：当我们引入hashmap，只保存向量的非零部分，那么这样对于稀疏向量的多次调用会节省大量的计算

时间复杂度： O(N)

空间复杂度：O(L)  L为非零部分的size

class SparseVector {
    Map map;
    SparseVector(int[] nums) {
        map = new HashMap();
        for(int i=0;i){
            if(nums[i]!=0) map.put(i,nums[i]);
        }
    }
    
    // Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int sum=0;
        for(int key:map.keySet()){
            if(vec.map.containsKey(key)){
                sum += map.get(key)*vec.map.get(key);
            }
        }
        return sum;
    }
}

followup：如果两个向量，只有一个是稀疏的，并且两个向量会非常非常大，无法使用hash，怎么办？

解法三：可以尝试只把它们放入list而不是hashmap，然后使用二分搜索进行匹配对应位置。

时间复杂度： O(N logL)

空间复杂度：O(L)  L为非零部分的size

class SparseVector {
    public List list;
    SparseVector(int[] nums) {
        list = new ArrayList();
        for(int i=0;i){
            if(nums[i]!=0) list.add(new Pair(i,nums[i]));
        }
    }
    // Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        //针对更稀疏的那个向量进行遍历，对另一个进行二分
        if(list.size()>vec.list.size())
            return dotResult(vec.list,list);
        else
            return dotResult(list,vec.list);
    }
    private int dotResult(List list1, List list2){
        int result = 0;
        for(Pair pair1:list1){
            //list1中的pair去list2中进行二分搜索匹配
            result += pair1.value*binarySearch(pair1.key, list2);
        }
        return result;
    }
    private int binarySearch(int pos, List list){
        int left = 0,right = list.size();
        while(left<right){
            int mid = left+(right-left)/2;
            System.out.println(pos+" "+left+" "+right+" "+mid);
            Pair curr = list.get(mid);
            if(curr.key > pos) right = mid;
            else if(curr.key < pos) left = mid+1;
            else return curr.value;
        }
        return 0;
    }
}
class Pair{
    public int key;
    public int value;
    Pair(int key,int value){
        this.key = key;
        this.value = value;
    }
}