有人问我这个问题我试图使用多数元素方法，但它对我不起作用请提供一些提示。
最佳答案
找出O(n)时间的中位数。
使用3向分区基于该中值对数组进行分区。
如果中值本身是必需的元素，则完成
其他的
在两个分区上（中间值的左和右）都应用多数元素算法。（在您的例子中，找到在n/2数组中出现超过n/4次的元素）两者都将在O(n)时间内运行。
总时间将3*O(n)=O(n)。
希望这有帮助：）
有人问我这个问题我试图使用多数元素方法，但它对我不起作用请提供一些提示。
最佳答案
找出O(n)时间的中位数。
使用3向分区基于该中值对数组进行分区。
如果中值本身是必需的元素，则完成
其他的
在两个分区上（中间值的左和右）都应用多数元素算法。（在您的例子中，找到在n/2数组中出现超过n/4次的元素）两者都将在O(n)时间内运行。
总时间将3*O(n)=O(n)。
希望这有帮助：）