wish面试题 count >=lengh/ 4数的解法

umialpha

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

最近在面Wish，找了地里的面经，发现有不少人都遇到这样的题目：从一个排好序的数组里找出出现次数大于length / 4的数。被这题挂的人也挺多，但是地里也没找到解题报告，这里贴一份我的报告，如果有什么不正确的地方，欢迎指正。

Solution:

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

everbelenger · 2018-10-14 01:13:24

另外楼主的答案是k*logn 时间复杂度

其实没必要binary search我感觉
k*(k)的负责度就能解决这题
# For each point, look around the k before and k after points.

wrxpy

啥职位

everbelenger · 2018-10-14 00:55:44

楼主的答案还是有一个小bug
print(find_popular([1, 2, 2, 4, 6, 7, 7], 4))
会漏掉7

everbelenger · 2018-10-14 00:58:29

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

umialpha · 2018-10-16 10:36:50

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

umialpha · 2018-10-16 10:51:58

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

Toby

遍历一遍统计word frequency, 再遍历一遍和n/4比较，对于unsorted array 也适用，time comp O(n)

umialpha

Toby 发表于 2018-11-6 23:18
遍历一遍统计word frequency, 再遍历一遍和n/4比较，对于unsorted array 也适用，time comp O(n)

对的。但是题目已经排好序了，所以最好还是用到这一条件.之前我看发帖的用O(n)复杂度的都挂了呃

seanyang

是要求必须O(1) space吗