Conduct Dot Product of two large Vectors
1. two pointers
2. hashmap
3. 如果没有额外空间，如果一个很大，一个很小，适合scan小的，并且在大的里面做binary search
1 package fb; 2 3 public class DotProduct { 4 5 public int dotPro(int[][] v1, int[][] v2) { 6 int[][] shortV; 7 int[][] longV; 8 if (v1.length < v2.length) { 9 shortV = v1; 10 longV = v2; 11 } 12 else { 13 shortV = v2; 14 longV = v1; 15 } 16 17 int res = 0; 18 for (int i=0; i<shortV.length; i++) { 19 int shortIndex = shortV[i][0]; 20 int shortValue = shortV[i][1]; 21 int longSeq = binarySearch(longV, shortIndex); 22 if (longSeq >= 0) { 23 res += shortValue * longV[longSeq][1]; 24 } 25 } 26 return res; 27 } 28 29 public int binarySearch(int[][] arr, int target) { 30 int l=0, r=arr.length-1; 31 while (l <= r) { 32 int m = (l+r)/2; 33 if (arr[m][0] == target) return m; 34 else if (arr[m][0] < target) l = m + 1; 35 else r = m - 1; 36 } 37 return -1; 38 } 39 40 41 /** 42 * @param args 43 */ 44 public static void main(String[] args) { 45 // TODO Auto-generated method stub 46 DotProduct sol = new DotProduct(); 47 int[][] v2 = new int[][]{{0,2},{1,3},{5,2},{7,1},{10,1}}; 48 int[][] v1 = new int[][]{{1,6},{7,2}}; 49 int res = sol.dotPro(v1, v2); 50 System.out.println(res); 51 } 52 53 }