【每日一题】今日面试题：熟悉的陌生人；及又见Google搜索之星分析

linggang_123

赞楼主。。。中午研究研究。。。

leewon1988

第二题的通用算法

1. /**
   
2. * 一个数组中有N个数字出现的次数都超过数组总长度L的1/(N+1)，查找这些ID
   
3. * */
   
4. 
   
5. #include <iostream>
   
6. #include <cstring>
   
7. #include <map>
   
8. #include <algorithm>
   
9. #include <utility>
   
10. using namespace std;
    
11. 
    
12. //数组：arr
    
13. //长度：size
    
14. //数字个数：n
    
15. map<int,int> find(int* arr,int size,size_t n)
    
16. {
    
17.         map<int,int> candidate;
    
18.         for(int i=0;i<size;++i)
    
19.         {
    
20.                 if(candidate.find(arr[i])!=candidate.end())
    
21.                 {
    
22.                         ++candidate[arr[i]];
    
23.                 }
    
24.                 else if(candidate.size()==n)
    
25.                 {
    
26.                         for(auto index=candidate.begin();index!=candidate.end();)
    
27.                         {
    
28.                                 --(index->second);
    
29.                                 if(index->second==0)
    
30.                                         candidate.erase(index++); //注意这里的写法，否则，index已经失效，将没办法遍历
    
31.                                 else
    
32.                                         ++index;                 //注意区别
    
33.                         }
    
34.                 }
    
35.                 else
    
36.                 {
    
37.                         candidate.insert(make_pair(arr[i],1));
    
38.                 }
    
39.         }
    
40.         return candidate;
    
41. }
    
42. 
    
43. int main(int argc,char* argv[])
    
44. {
    
45.         int arr[]={1,2,3,5,1,2,3};
    
46.         map<int,int> candidate=move(find(arr,sizeof(arr)/sizeof(int),3));
    
47.         for_each(candidate.begin(),candidate.end(),
    
48.                         [](const pair<int,int>& val)
    
49.                         {
    
50.                                 cout<<"Val: "<<val.first<<endl;
    
51.                         }
    
52.                         );
    
53.         return 0;
    
54. }
    

复制代码

leewon1988

第一题也很简单
就是判断是不是二分图
采用染色的方法