数据砖 店面

地里常见的设计数据结构。管理char。做到random insert, delete, read 都在线性以内。
insert(int index

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

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

就草草的聊了一下test case和时间复杂度的证明就结束了。估计是凉了。

题目是poj2887 解法看这里https://oi-wiki.org/ds/block-list/

我觉得除非知道这个元素的上界， 然后可以说定bucket大小为k， 这样插入是O(log(n/k)) + n(k) --> 因为要找到对应的bucket, 然后维护一个有序数组。  删除是O(log(n/k)) + O(k), read是O(log(n/k)).

如果不设上界， 那还是个线性算法。 预先知道上界， 可以设k = sqrt(n), 那样就是一个sqrt(n) 算法。

zqzned 发表于 2021-3-15 13:58
感觉每次更新都动一遍map有点麻烦
都有bucket list的话每次从头找就行
然后动态添加或者减少bucket

嗯 也可以 写好split和merge也可以 时间复杂度上更好..
我也跟面试官说了..他让我用map就好 我就懒得去想了.

hashmap + double linked list怎么做得？

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

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

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

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

感觉不需要用hashmap, 直接上buckets就行

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

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

zqzned 发表于 2021-3-14 15:14
感觉不需要用hashmap, 直接上buckets就行

对。维护两个方向也可以。。就是更新bucket reference的时候比较麻烦。。map的话 就遍历一遍next/prev就完事了。

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

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