FB电面

oi02lyl 发表于 2018-3-20 04:56
请问找median可以二分答案吗？

你是说用QuickSelect找到第n/2个元素？那个算法复杂度是O(n)的，比merge M sorted array这种n log m的要快，但是需要一个大数组把m个数组连续的存下来。

houqingniao 发表于 2018-3-18 04:47
m个array, 每个有n个elements，复杂度应该是 mnlogm

用priority_queue维护m个元素（各array当前元素），一共进行n/2步，所以是n log m的，你说的m n log m里面第一个m哪来的？

电面就求M个sorted array的median。。。可以可以

谢谢分享～～～～～～

降到100好嘛～～～～～～～～

请问楼主面一个小时吗？

jtqv84 发表于 2018-3-21 22:12
用priority_queue维护m个元素（各array当前元素），一共进行n/2步，所以是n log m的，你说的m n log m里 ...

一共是多少个elements呢？m*n

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

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

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

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