大佬教程收集整理的这篇文章主要介绍了1570. Dot Product of Two Sparse Vectors，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
For sparse venctors, there might be too many "0"s in the array. @R_607_10112@ we need to do is only abstract the items which are not "0". We store these non-zero items in HashMap or HashSet.
The HashMap solution is as following:
class SparseVector { Map<Integer, Integer> map = new HashMap<>(); SparseVector(int[] nums) { for(int i=0;i<nums.length;i++){ if(nums[i]!=0){ map.put(i, nums[i]); } } } // Return the dotProduct of two sparse vectors public int dotProduct(SparseVector veC) { Map<Integer, Integer> map1 = this.map; Map<Integer, Integer> map2 = vec.map; if(map1.size()>map2.size()){ //this is for follow up question return vec.dotProduct(this); } int sum = 0; for(Integer key: map1.keySet()){ if(map2.containsKey(key)){ sum+=map1.get(key)*@H_550_8@map2.get(key); } } return sum; } }
For follow up question: @R_607_10112@ if only one of the vectors is sparse?
The answer is, we compare the two HashMaps, we iterate the HashMap which has a smaller size.
We can also use HashSet to store the index of the nums, and get value from nums.
class SparseVector { Set<Integer> set = new HashSet<>(); int[] nums; SparseVector(int[] nums) { this.nums = nums; for(int i=0;i<nums.length;i++){ if(nums[i]!=0){ set.add(i); } } } // Return the dotProduct of two sparse vectors public int dotProduct(SparseVector veC) { Set<Integer> set1 = this.set; Set<Integer> set2 = vec.set; if(set1.size()>set2.size()){ //this is for follow up question return vec.dotProduct(this); } int sum = 0; for(Integer i: set1){ if(set2.contains(i)){ sum+=nums[i]*vec.nums[i]; } } return sum; } }
以上是大佬教程为你收集整理的1570. Dot Product of Two Sparse Vectors全部内容，希望文章能够帮你解决1570. Dot Product of Two Sparse Vectors所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。