内容简介：Given an array of size给定一个尺寸为你可以假定数组非空，并且一定存在多数元素。
Given an array of size n , find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
给定一个尺寸为 n 的数组，找到 多数元素 。所谓 多数元素 我们指的是出现次数超过 n/2 次的元素。
你可以假定数组非空，并且一定存在多数元素。
例1:
Input:[3,2,3]
Output:3
例2:
Input:[2,2,1,1,1,2,2]
Output:2
我们提供三个解：Hashmap解，分而治之解和 排序 解。
Hashmap解
这个思路很简单，就是用hashmap来保存对元素的统计信息。第一遍循环统计每个元素的出现次数。第二个循环找到出现最频繁的元素，即为结果。事实上这个代码可以轻松地改为hashmap一遍循环，能稍微快一点点，但是没有啥复杂度级别的提升，我就懒得改了。
分而治之解
因为 多数元素 出现的次数超过一半，所以不管它的分布，它在左右两边，必然有一边占有优势，在切分也会有类似的情况。所以我们对等切分即可，这还是个Mergesort的变种问题。
排序解
先把数组排序，然后统计元素出现频率，超过半数则为 多数元素 。（后来，我看了一个别人的解很简洁，先排序，然后中间的元素一定是 多数元素 。略绕，但是仔细想想还真是。我就不写这个实现了）
Github 地址： https://github.com/tinyfool/leetcode/tree/master/src/p0169
也请参阅我的文章《 LeetCode专题 分而治之 》，文章中实现了算法导论里面的这三个分而治之的问题的代码，以及LeetCode相关问题的一个列表。
以上所述就是小编给大家介绍的《LeetCode 第169题 Majority Element【分而治之】（Java）》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
