FB面经 稀疏矢量乘积

有序情况如下，使用双指针即可

class Node{
int index;
int value;
public Node(int index, int value);
}
//O(M+N)
public sparseVectorDotProduct(int v1[], int v2[]){
    List<Node> l1 = new ArrayList<Node>();
    List<Node> l2 = new ArrayList<Node>();
    for(int i = 0; i< v1.length; i++){
        if(v1[i]!=0)l1.add(new Node( i, v1[i]));
    }
    for(int j = 0; j<v2.length; j++){
        if(v2[j]!=0) l2.add(new Node( j, v2[j]));
    }
    int i = 0; j = 0, res = 0;
    while( i < l1.size() && j < l2.size() ){
        if(l1.get(i).index == l2.get(j).index){
            res += l1.get(i++).value * l2.get(j++).value;
        }
        else if( l1.get(i).index < l2.get(j).index) i++;
        else j++;
    }
    return res;
}

一个很长一个很短的话，遍历短矢量，对长矢量二分搜索