森鲜的脸家店面

很有用的问题，可惜今天大米用完了，就回帖支持lz一下吧

follow up 1， c++的话用一个unordered_map和一个数组存unordered_map的iterator，这样insert和popRandom都可以O(1)

1. //original
   
2. vector<int> nums;
   
3. 
   
4. void insert(int num)
   
5. {
   
6.     nums.push_back(num);
   
7. }
   
8. 
   
9. void popRandom()
   
10. {
    
11.     int n = nums.size();
    
12. 
    
13.     int i = rand() % n;
    
14.     nums[i] = nums.back();
    
15.     nums.pop_back();
    
16. }
    
17. 
    
18. //follow up 1
    
19. #define It unordered_map<int, int>::iterator
    
20. unordered_map<int, int> maps; //{num, freq}
    
21. vector<It> it_array;
    
22. 
    
23. void insert_followup_1(int num)
    
24. {
    
25.     It it = maps.find(num);
    
26. 
    
27.     if (it == maps.end()) {
    
28.         maps[num] = 1;
    
29.         it = maps.find(num);
    
30.         it_array.push_back(it);
    
31.     } else {
    
32.         it->second++;
    
33.     }   
    
34. }
    
35. 
    
36. void popRandom_followup_1()
    
37. {
    
38.     int n = maps.size();
    
39.     int i = rand() % n;
    
40. 
    
41.     It it = it_array[i];
    
42.     if (--it->second == 0) {
    
43.         maps.erase(it);
    
44.         it_array[i] = it_array.back();
    
45.         it_array.pop_back();
    
46.     }   
    
47. }

复制代码

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

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