狗家店面

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

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

感谢分享～顺祝offer～！！

应该没啥问题, 很标准的map 或者 二分搜索

可能没问太深吧, 比如query 很多的话存map好一点, 数字特别多的话sorting不方便怎么办, 如果是streaming data不能存怎么办, 数字大小限制有没有类似这种把..

肥宅快乐水 发表于 2018-8-15 04:05
应该没啥问题, 很标准的map 或者 二分搜索

可能没问太深吧, 比如query 很多的话存map好一点, 数字特别多 ...

请问query很多的话为什么存map会好些？如果是stream data的话直接数不行吗？

数字大小可能会是个问题，忽略了。

lz好运啊

leoloe326 发表于 2018-8-15 04:42
请问query很多的话为什么存map会好些？如果是stream data的话直接数不行吗？

数字大小可能会是个问题 ...

好像也没什么, 我瞎说的.

多次query每次都是lgn 那不就变成nlgn{:8_248:}

大哥对楼主的解法不太理解 楼主你二分是用的 start + 1 < end跳出循环吗

oo小天使oo 发表于 2018-8-15 08:27
大哥对楼主的解法不太理解 楼主你二分是用的 start + 1 < end跳出循环吗

差不多吧，不过我是判断lo和hi重合，跳出循环，得到的的是target-1最右和target+1最左的index，事实上就算这两个值不存在也能返回相应的index。

用两次BS，第一次找target最早的位置，第二次找target最后的位置，O(logN)

https://www.geeksforgeeks.org/count-number-of-occurrences-or-frequency-in-a-sorted-array/