169. 多数元素

题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ? n/2 ? 的元素。
解法一：暴力法
思路：先排序，然后统计元素出现次数，当出现后面的元素与前一个不同时，前一个元素的次数统计完毕，只需与n/2比较即可
代码：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
int count =1;
int i =1;
for(i =1;i<nums.length;i++){
if(nums[i]!=nums[i-1]){
if(count>nums.length/2){
return nums[i-1];
} else{
count =1;
}
} else{
count++;
}
}
return nums[i-1];
}
}

解法二：排序法
思路：排好序后，出现次数大于n/2的元素一定会出现在n/2位置上
代码：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}

解法三：分治法
思路：若左半部分和右半部分出现次数最多的元素相同，则该元素就是所找的答案，否则要遍历当前数组，确定出现次数
代码：
class Solution {
public int majorityElement(int[] nums) {
return findMaxTime(nums,0,nums.length-1);
}

public int findMaxTime(int[] nums,int l,int r){
    if(l==r){   //只有一个元素，众数就是它
        return nums[l];
    }    
    int m = (l+r)/2;
    int lElement = findMaxTime(nums,l,m);
    int rElement = findMaxTime(nums,m+1,r);
    if(lElement==rElement){ //左半部分和右半部分出现次数最多的元素相同，则该元素就是解
        return lElement;
    }
    //若不满足上述情况，则需要计算两个元素具体的出现次数，再比较
    int lElementTime = countMaxTime(nums,lElement,l,r);
    int rElementTime = countMaxTime(nums,rElement,l,r);
    return lElementTime>rElementTime?lElement:rElement;
}

public int countMaxTime(int[] nums,int target,int l,int r){
    int count = 0;
    for(int i =l;i<=r;i++){
        if(nums[i]==target){
            count++;
        }
    }
    return count;
}

}

解法四：摩尔投票法
思路：一定有某个候选人票数是多于一半的，即再怎么抵消票数也会>0
代码：
class Solution {
public int majorityElement(int[] nums) {
//注意一定有解这个条件
int condidate=nums[0], count=1; //先将0号元素作为最大希望候选人
for(int i=1;i<nums.length;i++){
if(nums[i]condidate){
count++; //支持的票数+1
} else{
if(count0){ //如果i不投给候选人并且候选人已经0票，则将候选人换为nums[i]
condidate = nums[i];
count = 1;
} else{
count--;
}
}
}
return condidate;
}
}

169. 多数元素

原文：https://www.cnblogs.com/nickyBlog/p/13922592.html