Thumbtack 店面经

问了一个很简单的题目，astream of integers

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

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

sk上二分找median的做法，但是这个似乎不是他期望的答案。

格格笑 发表于 2017-10-24 13:20
所以现在有想法了嘛？  O（1）做  32int

请看我的回帖！

我觉得可以造两个heap来存吧，这样即使是数值很大也无关紧要了。可以参见：https://leetcode.com/problems/fi ... stream/description/

lcq123 发表于 2017-8-14 09:08
我觉得可以造两个heap来存吧，这样即使是数值很大也无关紧要了。可以参见：https://leetcode.com/problems/ ...

要constant memory..
两个heap就全存下来O(n)了

wsteg 发表于 2017-9-27 10:39
要constant memory..
两个heap就全存下来O(n)了

所以现在有想法了嘛？  O（1）做  32int

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

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

格格笑 发表于 2017-10-24 13:20
所以现在有想法了嘛？  O（1）做  32int

数值范围到32位也是一样的吧，只是 N = 2^32 = 4G，每个数值用4 bytes来count出现的次数的话，相当于需要16G Bytes的内存，对现在的机器来说不是什么问题

cnt[1000] 算 O(1) 吗？

挖坟回帖

我觉得能不能开一个cnt[32]，把binary的每一位count下来？

这样的话就不需要16GB的内存了吧？

LanceZZZ 发表于 2018-3-16 04:24
挖坟回帖

我觉得能不能开一个cnt[32]，把binary的每一位count下来？

挖坟回挖坟回帖

能具体说说吗，开32位数组记录每一个数字的每个bit的count，然后呢？