Java面试经典 150 题.P169. 多数元素（005）
本题来自：力扣-面试经典 150 题
面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台
https://leetcode.cn/studyplan/top-interview-150/
题解：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}思路如下：
排序后由于多数多数元素占整个数组的1/2以上。所以数组中间一定是多数元素
题解：
class Solution {
public int majorityElement(int[] nums) {
int key = 0;
int value = 0;
for(int x : nums){
if(value == 0)
key = x;
if(key == x)
value++;
else
value--;
}
return key;
}
}思路如下：
Boyer-Moore 投票算法,如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。