给一个排序数组，找到element出现次数>n/3次，算法复杂度低于O(n)

有人有什么好的做法吗？

简单的想法：
A[n/3]和A[2n/3]中的至少一个点必定是答案，
如果A[n/3]==A[2n/3]，那就是答案了，
不是的话用二分法找A[n/3]和A[2n/3]的长度。

这题我记得是careercup原题

1.把整个数组拆成6个区间，分别验证各自头尾，如果A[n/3]存在必有至少一个区间的头尾是相等的，头尾相等的记1，不等记0，形成一个类似于[0,0,1,0,0,0]的数组B，B里面必须有至少一个元素为1，O(1)
2.B有两个相邻元素为1的情况立刻得出答案。O(1)
3.B没有相邻同为1的元素，但头尾位置出现1，比如B[0]=1，则只需要比较第1区间的尾和第0区间的头。O(1)
4.B没有相邻同1元素，中间有一个两边均为0的1元素，则从前后区间的中间开始折半查找。比如B=[0,1,0,0,0,0]，则先比较i=B[0][n/12]和j=B[2][n/12]设B[1]中元素均为k:
A[i]<k:比较区间往右挪；A[j]>k:比较区间往左挪。O(logn)

lc原题
https://leetcode.com/problems/majority-element-ii/#/description

Boyer-Moore算法变种, O(n)时间复杂度，O(1)空间复杂度

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

realchange 发表于 2017-5-18 23:02
lc原题
https://leetcode.com/problems/majority-element-ii/#/description

楼主问的是排序数组。。二楼的方法是对的。。