请教fb一个面经题

看到很多面经有提到 那个

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

分感谢！

两个sparse vector求点乘乘积。
基本做法是每个vector维护成{index -> value} 的hashtable, 复杂度是O(min(n, m))，但是hashtable会浪费额外空间。
空间优化方法是维护vector< pair<index, value>>。

同问。。感觉这题频率好高

1. 
   
2. class Solution{
   
3. public:
   
4.         int dotProduct(vector<pair<int,int>>& v1,vector<pair<int,int>>& v2){
   
5.                 int res=0;
   
6.                 unordered_map<int,int> m;//key: position  value: val
   
7.                 for(auto&& v:v1){
   
8.                         m[v.first]=v.second;
   
9.                 }
   
10.                 for(auto&& v:v2){
    
11.                         if(m.find(v.first)!=m.end()){
    
12.                                 res+=v.second*m[v.first];
    
13.                         }
    
14.                 }
    
15.                 return res;
    
16.         }
    
17. };
    
18. 
    
19. class Solution2{
    
20. public:
    
21.         int dotProduct(vector<pair<int,int>>& v1,vector<pair<int,int>>& v2){
    
22.                 sort(v1.begin(),v1.end(),[](pair<int,int> i,pair<int,int> j){
    
23.                                 return i.first<j.first;
    
24.                                 });
    
25.                 sort(v2.begin(),v2.end(),[](pair<int,int> i,pair<int,int> j){
    
26.                                 return i.first<j.first;
    
27.                                 });
    
28.                 int i=0,j=0,res=0;
    
29.                 while(i<v1.size()&&j<v2.size()){
    
30.                         if(v1[i].first<v2[j].first)
    
31.                                 i++;
    
32.                         else if(v1[i].first>v2[j].first)
    
33.                                 j++;
    
34.                         else{
    
35.                                 res+=v1[i].second*v2[j].second;
    
36.                                 i++;
    
37.                                 j++;
    
38.                         }
    
39.                 }
    
40.                 return res;
    
41.         }
    
42. };

复制代码

懂了！谢谢各位！

mark。。。。