这是LeetCode上的一道算法题,博主整理了三种解题思路和方法,希望可以帮助大家提升算法的思维。
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:[3,2,3] 输出:3
示例 2:
输入:[2,2,1,1,1,2,2] 输出:2
进阶:
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
来源:力扣(LeetCode) 链接:169.多数元素
这是一个时间复杂度为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;
}
举个例子:
当把这些数字排好序后,出现次数 >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),所以这个解法还不够完美。
下面介绍一个巨牛的时间复杂度只有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。