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