_1570.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.List;

publicclass_1570 {
publicstaticclassSolution1 {
/*
 * This is a brute force but accepted solution.
 */
classSparseVector {
int[] vector;

SparseVector(int[] nums) {
this.vector = nums;
 }

// Return the dotProduct of two sparse vectors
publicintdotProduct(SparseVectorvec) {
int[] incoming = vec.vector;
intdotProduct = 0;
for (inti = 0; i < vector.length; i++) {
dotProduct += incoming[i] * this.vector[i];
 }
returndotProduct;
 }
 }
 }

publicstaticclassSolution2 {
/*
 * More optimal solution:
 * 1. use a map to store only non-zero values to save space;
 * 2. loop through the smaller list;
 * 3. use binary search to find the corresponding index in the bigger list if it exists;
 */
classSparseVector {
privateList<int[]> indexAndNumList;

SparseVector(int[] nums) {
this.indexAndNumList = newArrayList<>();
for (inti = 0; i < nums.length; i++) {
if (nums[i] != 0) {
this.indexAndNumList.add(newint[] {i, nums[i]});
 }
 }
 }

// Return the dotProduct of two sparse vectors
publicintdotProduct(SparseVectorvec) {
List<int[]> incoming = vec.indexAndNumList;
if (incoming.size() < this.indexAndNumList.size()) {
returndotProduct(incoming, this.indexAndNumList);
 } else {
returndotProduct(this.indexAndNumList, incoming);
 }
 }

privateintdotProduct(List<int[]> smaller, List<int[]> bigger) {
intproduct = 0;
for (int[] indexAndNum : smaller) {
int[] exists = binarySearch(bigger, indexAndNum[0]);
if (indexAndNum[0] == exists[0]) {
product += indexAndNum[1] * exists[1];
 }
 }
returnproduct;
 }

privateint[] binarySearch(List<int[]> indexAndNumList, inttarget) {
intleft = 0;
intright = indexAndNumList.size() - 1;
int[] result = newint[] {-1, 0};
if (indexAndNumList.get(right)[0] < target
 || indexAndNumList.get(left)[0] > target) {
returnresult;
 }
while (left <= right) {
intmid = left + (right - left) / 2;
if (indexAndNumList.get(mid)[0] == target) {
returnindexAndNumList.get(mid);
 } elseif (indexAndNumList.get(mid)[0] > target) {
right = mid - 1;
 } else {
left = mid + 1;
 }
 }
returnnewint[] {-1, 0};
 }
 }
 }
}