脸家电面

luyulzs 发表于 2020-2-25 09:45
多谢你的回答，我怎么忘记线段树了！

店面不可能考这个的吧，线性扫两遍应该就是标准答案了

convexopt 发表于 2020/02/25 09:49:50
店面不可能考这个的吧，线性扫两遍应该就是标准答案了

应该不会，我刚刚通知过了应该线性扫描是可以的。为了造福后人可以让他们在面试提一下线段树的方法作为improvement方法的followup答案应该可以增加过的几率。

luyulzs 发表于 2020-2-25 09:53
应该不会，我刚刚通知过了应该线性扫描是可以的。为了造福后人可以让他们在面试提一下线段树的方法作为imp ...

我又想了一下，这是个离线问题，也就是说只需要直方图最后的状态，所以也可以这样做：

维护一个长度2M+2的数组，对每一个区间先取和[-M,M]的交集，归一化，然后做如下更新

[1 3] & [-5 5]  + 5 => [6, 8]     [0 0 0 0 0 -1 0 0 1 0 0    0]
                                               0 1 2 3 5  6 7 8 9 10 11 12

[4 5] & [-5 5]  + 5 =>[10, 11]    [0 0 0 0 0 -1 0 0 1 -1   0   1]
                                                0 1 2 3  5  6 7 8 9 10 11 12

[-5 2] & [-5 5]  + 5 =>[0, 7]     [-1 0 0 0 0 -1 0 1 1 -1   0   1]
                                                0 1 2 3  5  6 7 8 9 10 11 12

最后从左到右做后缀和得到最后的直方图
[0 1 1 1 1 1 2 2 1 0   1   1]
  0 1 2 3 5 6 7 8 9 10 11 12

这里的下标总共偏移了6，减去6后得到最大的两项是1,2

如果有N个区间，复杂度是O(MN)，全部都扫的话是O(M^2N)

convexopt 发表于 2020-2-25 09:35
我觉得这题和meeting room不一样，
1. Meeting room 里任何区间的重合都算，这题必须在[-M, M]这个范围 ...

我不知道是不是我没理解题意？我还是看不出来为什么不能用meeting room算？因为出现最多的数字第一个肯定是一个start point，题目不是说随便输出一个就好了吗？用一个counter计算有多少个重合的interval，增长的时候记录一下start point。这样不可以吗？-M，M感觉无所谓吧？

cloudycloud 发表于 2020-2-25 12:25
我不知道是不是我没理解题意？我还是看不出来为什么不能用meeting room算？因为出现最多的数字第一个肯定 ...

如果重合的部分不在[-M M]里就不能算啊

convexopt 发表于 2020-2-25 12:55
如果重合的部分不在[-M M]里就不能算啊

我觉得这个判断一下就可以吧？比如说如果M是3.然后给了一个{[-5, -2], [-6, -1]}。扫的时候如果不在range就不作数

             -6   -5    -2    -1   
cnt          1    2     1     0     
maxInt    0    0     1     0     
result                  -2

cloudycloud 发表于 2020-2-25 13:04
我觉得这个判断一下就可以吧？比如说如果M是3.然后给了一个{[-5, -2], [-6, -1]}。扫的时候如果不在range ...

不在range的话直接丢掉估计也不对，可以先把交集算出来再这样扫

convexopt 发表于 2020-2-25 13:15
不在range的话直接丢掉估计也不对，可以先把交集算出来再这样扫

哦可能是我没太懂题的意思

第二题的话，是不是用一个hashmap过一遍所有的internval，然后找hashmap里面出现最多的数字即可，没必要把[-m,m] 里面所有的数字都走一遍吧

llatjob 发表于 2020/02/25 22:37:42
第二题的话，是不是用一个hashmap过一遍所有的internval，然后找hashmap里面出现最多的数字即可，没必要...

可以这样做平均的时间复杂度其实是一样的。因为大头在扫intervals的array。特殊情况除外。另外array读写速度快于hashmap，可以作为tradeoff提一下