Dot Product.java

import java.util.ArrayList;
import java.util.List;


public class Solution {
    //普通两个数组的点乘
    public int dotProduct(int[] a, int[] b) {
        int len = a.length;
        int res = 0;
        for (int i = 0; i < len; i++) {
            res += a[i] * b[i];
        }
        return res;
    }

    //follow1: Sparce, long and short 稀疏矩阵点乘（很多个0）
    class Tuple{ //元组
        int val,index;
        Tuple(int val,int index){
            this.val=val;
            this.index=index;
        }
    }
    //follow1 方法1：O(m*n) 只把非零元素加入list中，比较index相等的时候才相乘累加
    public int SparseVectorProduct(int[] a, int[] b) {
        int res = 0;
        List<Tuple> l1 = new ArrayList<>();
        List<Tuple> l2 = new ArrayList<>();  //两个list里面只放有效非零元素
        for (int i = 0; i < a.length; i++) {
            if (a[i] != 0) l1.add(new Tuple(a[i], i));
        }
        for (int i = 0; i < b.length; i++) {
            if (b[i] != 0) l2.add(new Tuple(b[i], i));
        }
        for (Tuple t1 : l1) {
            for (Tuple t2 : l2) {
                if (t1.index == t2.index) res += t1.val * t2.val;
            }
        }
        return res;
    }

    //follow1 方法2：O（m+n）, 2pointers
    // 两根指针分别指两个list的头，开始往后遍历。index1<index2,就不断后移指针1；否则后移指针2；知道两者相等，开始运算累加
    int i = 0, j = 0;
    while(i < l1.size() && j < l2.size()){
        while (l1.get(i).index < l2.get(j).index) i++;
        if (l1.get(i).index == l2.get(j).index) {
            res += l1.get(i).val * l2.get(j).val;
            i++;
            j++;
        }
        while (l1.get(i).index > l2.get(j).index) j++;
    }


    //follow2: sparse 稀疏矩阵，两个数组一长一短long and short，二分:在长数组里找短数组的每个元素，比较下标，相等就处理
    //  O(n*logm)
    int i = 0, j = l2.size() - 1;
    for(Tuple t1:l1){//短的那个  t1为target
        while (i <= j) {
            int mid = (j - i) / 2 + i;
            if (l2.get(mid).index == t1.index) res += t1.val * l2.get(mid).val;
            if (l2.get(mid) < t1.index) j = mid;
            else i = mid + 1;
        }
    }
}