Nuro 店面面经

PGGq5gplQ0Gn 发表于 2021-2-10 04:34
用线段树来维护就可以了，搜是logk,更新也是logk.

你的意思是，每个元素的权重都为1，用线段树来表示每个范围的权重和。
然后采样的时候每选取一个元素，就把它的权重更新为0？

补充内容 (2021-2-14 11:45):
我再重新整理一下。

之前楼上有说用presum+binary search可以解决有放回的情况。换成线段树就可以处理无放回的情况，还是类似presum，从左到右遍历线段树的叶子然后找到第一个权重和大于随机数的叶子。楼下有代码

PGGq5gplQ0Gn 发表于 2021-2-10 04:34
用线段树来维护就可以了，搜是logk,更新也是logk.

构造线段树的复杂度是O(n)也不满足要求吧
=============================

编辑：不好意思没审清题目

如果只是要求sample的复杂度为O(logn)的话用线段树是可以（不好意思这里的n是楼主的k）

1. class SamplingSegmentTree {
   
2. public:
   
3.     SamplingSegmentTree(const vector<int>& weights) {
   
4.         num_elements_ = weights.size();
   
5.         weight_nodes_.resize(4 * num_elements_);
   
6.         Construct(weights, 0, num_elements_ - 1, 0);
   
7.     }
   
8.    
   
9.     int Sample() {
   
10.         int target_weight = rand() % weight_nodes_[0];
    
11.         int selected = -1;
    
12.         Sample(0, num_elements_ - 1, 0, target_weight, selected);
    
13.         return selected;
    
14.     }
    
15.    
    
16. private:
    
17.     size_t num_elements_;
    
18.     vector<int> weight_nodes_;
    
19.    
    
20.     void Construct(const vector<int>& weights, int wl, int wr, int t) {
    
21.         if (wl > wr) return;
    
22.         if (wl == wr) {
    
23.             weight_nodes_[t] = weights[wl];
    
24.         } else {
    
25.             int tl = 2 * t + 1;
    
26.             int tr = 2 * t + 2;
    
27.             int wm = wl + (wr - wl) / 2;
    
28.             Construct(weights, wl, wm, tl);
    
29.             Construct(weights, wm + 1, wr, tr);
    
30.             weight_nodes_[t] = weight_nodes_[tl] + weight_nodes_[tr];
    
31.         }
    
32.     }
    
33.    
    
34.     void Sample(int wl, int wr, int t, int& target_weight, int& selected) {
    
35.         if (selected != -1) return;
    
36.         if (wl > wr) return;
    
37.         if (wl == wr) {
    
38.             target_weight -= weight_nodes_[t];
    
39.             if (target_weight < 0) {
    
40.                 selected = wl;
    
41.                 weight_nodes_[t] = 0;
    
42.             }
    
43.         } else {
    
44.             int tl = 2 * t + 1;
    
45.             int tr = 2 * t + 2;
    
46.             int wm = wl + (wr - wl) / 2;
    
47.             Sample(wl, wm, tl, target_weight, selected);
    
48.             Sample(wm + 1, wr, tr, target_weight, selected);
    
49.             weight_nodes_[t] = weight_nodes_[tl] + weight_nodes_[tr];
    
50.         }
    
51.     }
    
52. };
    
53. 
    
54. int main() {
    
55.     map<string, int> distribution;
    
56.     for (int i = 0; i < 100000; ++i) {
    
57.         SamplingSegmentTree sst({1,1,1,1,1});
    
58.         vector<int> sample;
    
59.         for (int j = 0; j < 3; ++j) {
    
60.             sample.push_back(sst.Sample());
    
61.         }
    
62.         sort(sample.begin(), sample.end());
    
63.         string key;
    
64.         for (int s: sample) key += to_string(s) + " ";
    
65.         ++distribution[key];
    
66.     }
    
67.     for (auto& entry : distribution) {
    
68.         cout << entry.first << ": " << entry.second << endl;
    
69.     }
    
70. }

复制代码

输出结果：

1. 0 1 2 : 10063
   
2. 0 1 3 : 10054
   
3. 0 1 4 : 10092
   
4. 0 2 3 : 9803
   
5. 0 2 4 : 10025
   
6. 0 3 4 : 10018
   
7. 1 2 3 : 9945
   
8. 1 2 4 : 9944
   
9. 1 3 4 : 9964
   
10. 2 3 4 : 10092

复制代码

jgao93 发表于 2021-2-14 11:14
如果只是要求sample的复杂度为O(logn)的话用线段树是可以（不好意思这里的n是楼主的k

void SamplingSegmentTree::Sample(int wl, int wr, int t, int& target_weight, int& selected); 的部分还可以再优化一下：

1.     void Sample(int wl, int wr, int t, int& target_weight, int& selected) {
   
2.         if (selected != -1) return;
   
3.         if (wl > wr) return;
   
4.         if (weight_nodes_[t] <= target_weight) {
   
5.             target_weight -= weight_nodes_[t];
   
6.             return;
   
7.         }
   
8.         
   
9.         if (wl == wr) {
   
10.             target_weight -= weight_nodes_[t];
    
11.             selected = wl;
    
12.             weight_nodes_[t] = 0;
    
13.         } else {
    
14.             int tl = 2 * t + 1;
    
15.             int tr = 2 * t + 2;
    
16.             int wm = wl + (wr - wl) / 2;
    
17.             Sample(wl, wm, tl, target_weight, selected);
    
18.             Sample(wm + 1, wr, tr, target_weight, selected);
    
19.             weight_nodes_[t] = weight_nodes_[tl] + weight_nodes_[tr];
    
20.         }
    
21.     }

复制代码

jgao93 发表于 2021-2-14 12:20
void SamplingSegmentTree::Sample(int wl, int wr, int t, int& target_weight, int& selected); 的部分 ...

这部分写错了，写成了带权重每个元素仅有一个的算法。应该是每个元素有多个，所以选中元素的weight_nodes_不应该更新为0，应该减1.

1.         if (wl == wr) {
   
2.             target_weight -= weight_nodes_[t];
   
3.             selected = wl;
   
4.             --weight_nodes_[t];
   
5.         }

复制代码