M家电面

11/9 电面

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

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

pantomath 发表于 2021-11-10 15:10
我一直很好奇 而幺吴 直接来个Arrays.sort 会怎么样

会被挂掉

lz这是二分专场

匿名者 发表于 2021-11-11 14:56
不一定distinct，当时题里有写判断条件 >=

了解了 感谢！
请问那lz的二分是不是还是像LC find peak那题差不多呀
left, right = 0, len(nums) - 1
然后判断的条件是：
if nums[mid] <= nums[mid + 1]:
    right = mid
else:
    left = mid +1

想问下楼主第二题 quick select，time complexity怎么答的

我一直很好奇 而幺吴 直接来个Arrays.sort 会怎么样

请问楼主第一题的意思是不是目标值只可能在array中间？不可能是边界？

luntans 发表于 2021-11-10 17:12:12
请问楼主第一题的意思是不是目标值只可能在array中间？不可能是边界？

边界也可以 assume必有local minimum

匿名用户 发表于 2021-11-10 14:53:16
想问下楼主第二题 quick select，time complexity怎么答的

ave O(n), worst O(n^2)

ke_lingyun 发表于 2021-11-10 19:42
ave O(n), worst O(n^2)

嗯嗯，我也感觉是

ke_lingyun 发表于 2021-11-10 17:32
边界也可以 assume必有local minimum

哦哦。那是不是假设边界之外是无穷大，比如一直单调递增的话，答案就是边界最左端？

匿名者 发表于 2021-11-10 14:53
想问下楼主第二题 quick select，time complexity怎么答的

O(N)吧，最坏情况（初识情况是完全倒序的，然后要找的是正过来的最后一个）是O(N^2)

所以需要随机选择pivot，或者先把整个数组shuffle一下，就能保证都是O(N)了