狗VO

orlandowzb 发表于 2022-07-19 12:23:31
关键是第二题，得到 counter 很容易，知道中位数，无论直接找 遍历找 key，还是 prefix 数组都不是 O(1)这个你有啥好想法吗

没想到有什么方法可以O(1)…这个太难了

第二题我的想法是，已知输入的是个整数，那么我们可以开辟一个数组，所有数初始化为0，每个数放入下标i的counter，其中2^i <= nun < 2^(i+1)。如果考虑负数的话就再加一个list。每次get的时候计算中位数位置即可。
因为int有4个字节，所以数组长度固定32，这样每次操作都是O(1)

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

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

StrRicher 发表于 2022-7-19 13:51
没想到有什么方法可以O(1)…这个太难了

看下文回复，似乎是想复杂了，本来很简单

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

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

orlandowzb 发表于 2022-7-19 12:47
应该这样做。重新给两个mxn 矩阵。一个是全 0，另一个矩阵的每个 element 的数值是周边 0 的个数。然后（ ...

多谢，但是没有相同这么做的逻辑，或者说具体做法

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

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

Falldawn 发表于 2022-7-19 16:49
多谢，但是没有相同这么做的逻辑，或者说具体做法

leetcode 有类似的上颜色和 garden 的。用 greedy，可以几行就写出来的

orlandowzb 发表于 2022-7-19 17:01
leetcode 有类似的上颜色和 garden 的。用 greedy，可以几行就写出来的

能给个题号嘛，多谢

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

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