【LeetCode】169.多数元素（三种解法）
问题描述
这是LeetCode上的一道算法题，博主整理了三种解题思路和方法，希望可以帮助大家提升算法的思维。
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3] 输出：3
示例 2：
输入：[2,2,1,1,1,2,2] 输出：2
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。来源：力扣（LeetCode） 链接：169.多数元素
一、解法1（双引用暴力求解）：
这是一个时间复杂度为O（n*n）的算法，也是大多数人能想出来的算法。 每次从数组中取出一个元素，扫描一遍数组，查看这个元素出现的次数，当前元素出现次数 >= n / 2,即为答案。 代码如下：
public static void main(String[] args) {
int[] arr = new int[]{2,2,1,1,1,2,2};
int sum = find(arr);
System.out.println(sum);
}
private static int find(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int count=0;//设置计数器来统计每个元素出现的次数
for (int j = 0; j < arr.length; j++) {
if (arr[i]==arr[j]){
count++;
}
}
if (count>arr.length/2){
//当前元素出现次数 >n / 2,即为答案
return arr[i];
}
}
return -1;
}二、解法2（排序后直接返回中间值）：
举个例子：
当把这些数字排好序后，出现次数 >n / 2的元素一定是数组中间的元素。 代码如下：
public static void main(String[] args) {
int[] arr = new int[]{2,2,1,1,1,2,2};
Arrays.sort(arr);
System.out.println(arr[arr.length >> 1]);
}由于排序算法的时间复杂度最优最快也是O（nlogn），所以这个解法还不够完美。
三、解法3（摩尔投票法）
下面介绍一个巨牛的时间复杂度只有O（n）的算法。（这个算法适用于任何众数问题）。
这个问题的本质就是候选人正票数和负票数的抵消问题，由于多数元素的得票数一定是>n/2，抵消后，票数一定是一个正数，最终胜出。
public static void main(String[] args) {
int[] arr = new int[]{2,2,1,1,1,2,2};
System.out.println(majorityElement(arr));
}
public static int majorityElement(int[] arr) {
// 默认候选人就是第一个元素
int candidate = arr[0];
int count = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == candidate) {
count++;
} else {
count--;
if (count == 0) {
// 更换候选人
candidate = arr[i];
count = 1;
}
}
}
return candidate;
}默认候选人就是第一个元素，然后给自己投一票（count=1），如果遇到相同的票则+1，否则-1。当count为0的时候换下一个人，并且重置票数为1（count=1）。
四、 总结（摩尔投票法的推广）
摩尔投票法的应用----众数问题 1.在一堆元素中，如果至多选择一个最多的元素，则他的票数>n/2. 2.在一堆元素中，如果之多选择两个最多的元素，则他的票数>n/3. 3.在一堆元素中，如果之多选择m个最多的元素，则他的票数>n/(m+1).
1.因为出现次数大于n/3的元素最多只有两个，所以最开始可以维护两个数字(num1,num2)和两个计数器(counter1,counter2)； 2.遍历数组，当数组中元素和num1或者num2相同，对应的counter1或者counter2加1； 3.如果counter1或counter2为0，将遍历到的该元素赋给num1或者nums2； 4.否则counter1和counter2都减1。
腾讯云开发者
