请教一个二分法的题

之前google面经里有的关于majority element的题，就是一个排序数组有n个值，求所有出现次数等于或者超过n / k的值。
比如[1 1 2 2 2 2 3 4 5 5 5 5]
k = 3
return [2,5]

知道是应该用binary search做，但是具体逻辑搞不太明白啊？

首先，target 只能是 n / k, 2n/k, ... ,(n - k) / k, 然后你对每一个target进行一次二分查找就好了，二分查找就是找最左边是这个数的（比如index1），最右边是这个数的(index2), 然后你用index2 - index1 看是不是符合题目要求了，把所有符合要求的都放在结果里面就好了。复杂度应该是 k*logN 吧？

根据题意，满足条件的点只可能出现在n/k,2n/k....,n  对这几个点用二分法求range，看看个数是否大于n/k.

jy_121 发表于 2016-5-30 12:54
根据题意，满足条件的点只可能出现在n/k,2n/k....,n  对这几个点用二分法求range，看看个数是否大于n/k.

能具体讲一讲怎么求range么？需要先比较n/k, 2n/k么？

comicrudy 发表于 2016-5-30 13:48
能具体讲一讲怎么求range么？需要先比较n/k, 2n/k么？

你去做下leetcode的search for range就知道了

jy_121 发表于 2016-5-30 14:04
你去做下leetcode的search for range就知道了

应该可以剪枝吧？不需要对每一个值都找完range。

维护一个K window，对这个K window 内的数求 one majority element?

不懂用binary search怎么做 不过lc easy里面有道差不多的 不过k固定是2 我直接遍历数组存hashmap里了....虽然很慢...等大神回复....

一个想法是：因为这个数组是排了序的 所以符合条件的数只可能在n/k n/2k...的位置上 因此只需要把这些位置的数前后出现次数加起来...