狗onsite面试

狗onsite两题：

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

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

小丸几 发表于 2019-5-2 15:56
露珠用的Median of medians还是quick select?

Quick select

richardleo 发表于 2019-2-19 22:18
想成已经排序的了，没排序的话可以用 k select.
也不是一定要求medium， 如果是n的元素，中间点即可

logN不对，排序了的直接O(1)，没排的用k select, O(n) (average)

第一题全部加起来取平均就行吧o（n）

为啥只有两题

1. Y坐标值 medium O(logN)

第一题难道就是排序后取中间那个数？

richardleo 发表于 2019/02/19 14:49:58
1. Y坐标值 medium O(logN)

请教y坐标 medium 怎么实现o(logN)呢 要排序的话不是O(nlogn)吗

kkchenk 发表于 2019/02/19 21:37:05


请教y坐标 medium 怎么实现o(logN)呢 要排序的话不是O(nlogn)吗

想成已经排序的了，没排序的话可以用 k select.
也不是一定要求medium， 如果是n的元素，中间点即可

第一题如果是奇数的话取中间那个左边，偶数的话中间两点间任意坐标

alinawxn 发表于 2019-2-19 23:52
第一题如果是奇数的话取中间那个左边，偶数的话中间两点间任意坐标

对的，就是取 Median.