LeetCode 第169题 Majority Element【分而治之】(Java)

原题地址:https://leetcode.com/problems/majority-element/

给定一个尺寸为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相关问题的一个列表。

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据