题目描述
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例1：
输入: [3,2,3]
输出: 3
示例2：
输入: [2,2,1,1,1,2,2]
输出: 2
方法一：暴力法
最简单的方法，两层循环，外层循环固定一个数，内层统计这个数出现的总次数。并且整个算法需要维护一个当前最大出现次数。时间复杂度为O(n^2)。
public int majorityElement(int[] nums) {
Arrays.sort(nums);
int i=0,j=0;
int max = -1;
int majority = -1; //众数
while(i<nums.length)
{
int count = 1;
for(j=i+1;j<nums.length;j++)
{
if(nums[j]==nums[i]) ++count;
else break;
}
if(max<count) {
max = count;
majority = nums[i];
}
if(max>nums.length/2) return majority;
i=j;
}
return -1;
}
运行时间6ms。
方法二：哈希
遍历一遍数组，放入HashMap中，记录该数字出现的次数。
public int majorityElement(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++)
{
if(!map.containsKey(nums[i])) map.put(nums[i],1);
else {
int count = map.get(nums[i]);
map.put(nums[i],++count);
}
}
int majority = -1, maxcount = -1;
for(HashMap.Entry<Integer,Integer> entry: map.entrySet())
{
int curcount = entry.getValue();
int curelem = entry.getKey();
if(maxcount < curcount) {
maxcount = curcount;
majority = curelem;
}
}
return majority;
}
运行时间39ms。
方法三：取中间下标
将数组排序以后，众数出现在中间位置。
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
方法四：随机过程
每次随机地选取一个元素，然后统计这个数出现的次数，如果大于数组长度的一半，说明已经找到了众数。这里写了几个辅助函数：
1.产生[min, max)的随机数。
private int formRand(Random rand,int min,int max) {
return rand.nextInt(max-min)+min;
}
2.计算某个元素出现次数。
private int countTime(int[] nums,int target) {
int count=0;
for(int i=0;i<nums.length;i++)
if(target==nums[i]) ++count;
return count;
}
3.主函数
public int majorityElement(int[] nums) {
Random rand = new Random();
int maxcount = nums.length/2;
while(true) {
int elem = nums[formRand(rand,0,nums.length)];
int count = countTime(nums,elem);
if(count > maxcount)
return elem;
}
}
运行时间5ms。
方法五：分治法
采用分治法思想，一个数组的众数可以理解为，左半部分的众数a，有伴部分的众数b。如果a==b,整个数组的众数就是a；否则，取a和b中出现次数更多的那个。分治法将问题分割，最小的情况是数组元素剩下一个，那么众数就是它本身。
private int majorityElement(int[] nums,int low,int high)
{
if(low==high) return nums[low];
int mid = (low+high)>>>1;
int leftElem = majorityElement(nums,low,mid);
int rightElem = majorityElement(nums,mid+1,high);
if(leftElem==rightElem) return leftElem;
int countLeft = countTime(nums,low,high,leftElem);
int countRight = countTime(nums,low,high,rightElem);
return countLeft>countRight?leftElem:rightElem;
}
public int majorityElement(int[] nums)
{
return majorityElement(nums,0,nums.length-1);
}
private int countTime(int[] nums,int low,int high,int target) {
int count=0;
for(int i=low;i<=high;i++)
if(target == nums[i]) ++count;
return count;
}
方法六：摩尔投票法（同归于尽法）
假设一个数列中，众数的得分为+1，非众数得分为-1，那么整个数列的和一定大于0。在此算法中，维护一个得分count，和当前选中的众数majority。进行一轮扫描，当扫描到的元素不等于当前众数时，--count；否则，++count。当count=0时，更换众数。
public int majorityElement(int[] nums){
int count = 0;
int majority = nums[0];
for(int i=0;i<nums.length;i++)
{
if(count==0)
majority = nums[i];
count += majority==nums[i]? 1:-1;
}
return majority;
}
运行时间4ms。
