利用摩尔投票算法解决LeetCode 169与229题

- 日理万妓 2022-03-10 01:58 154阅读 0赞

#### 摩尔投票算法是今天在[LeetCode 169(Majority Element)题][LeetCode 169_Majority Element]看到的算法.本篇文章将从本题出发探讨摩尔投票算法,并且利用本算法进而扩展解决[LeetCode 229(Majority Element2)题][LeetCode 229_Majority Element2].(本文使用Java编写代码) ####

## 一、LeetCode 169(Majority Element)原题介绍: ##

**给定一个大小为n的数组,找到其中出现次数超过元素总个数一半的数(出现次数>n/2).我们可以假设数组是非空的,并且给定的数组总是存在出现次数超过元素总个数一半的数.**

例题:  
输入: \[2,2,1,1,1,2,2\]  
输出: 2

例题分析: \[2,2,1,1,1,2,2\]这个数组元素总个数为7,一半为3.5,也就是说这个数组中需要有某个数的出现次数要大于3.5次,也就是至少是4次.其中2出现了4次,所以符合条件输出,而1出现了3次,不符合条件.

### 以下是常用的一些方法: ###

**1.遍历数组存入HashMap并计数,最后遍历HashMap输出符合条件的数**

Map<Integer, Integer> map=new HashMap<Integer, Integer>();
    int[] nums={2,3,1,4,1,5,5,5,5,5,5};
    for(int i=0;i<nums.length;i++){
    	if((map.get(nums[i]))==null){
    		map.put(nums[i], 1);
    }else{
    		int num=map.get(nums[i]);
    		map.put(nums[i], num+1);
    	}
    }
    Iterator<Integer> it=map.keySet().iterator();
    while(it.hasNext()){
    	int num=it.next();
    	if(map.get(num)>nums.length/2) {
    		System.out.println("大多数为:"+num);
    	}
    }

**2.排序法:对数组排序后,其中出现次数大于一半的肯定在中间**

int[] nums= {2,3,1,4,1,5,5,5,5,5,5};
    Arrays.sort(nums);
    System.out.println(nums[nums.length/2]);

## 二、LeetCode 169(Majority Element)的摩尔投票算法版: ##

int[] nums=new int[]{2,3,1,4,1,5,5,5,5,5,5};
    int maj=nums[0];
    int count=0;
    for(int i=0;i<nums.length;i++) {
    	if(count==0) {
    		maj=nums[i];
    		count=1;
    	}else if(maj==nums[i]) {
    		count++;
    	}else{
    		count--;
    	}
    }
    System.out.println(maj);

## 三、LeetCode 229(Majority Element2)的摩尔投票算法版: ##

int[] nums=new int[]{1,1,1,4,1,5,5,5,5,5,5};
    int maj1=nums[0];
    int maj2=nums[1];
    int count1=0;
    int count2=0;
    for(int i=0;i<nums.length;i++) { //算法核心，找出大多数的候选值
    	if(maj1==nums[i]) {
    		count1++;
    	}else if(maj2==nums[i]) {
    		count2++;
    	}else if(count1==0) {
    		maj1=nums[i];
    		count1=1;
    	}else if(count2==0) {
    		maj2=nums[i];
    		count2=1;
    	}else {
    		count1--;
    		count2--;
    	}
    }
    count1=0;
    count2=0;
    for(int i=0;i<nums.length;i++) { //统计确定候选值是真的大多数
    	if(nums[i]==maj1) {
    		count1++;
    	}else if(nums[i]==maj2) {  //使用else if避免当数组为[0,0,0]时,出现两个0为结果的情况
    		count2++;
    	}
    }
    if(count1>nums.length/3) {
    	System.out.println(maj1);
    }
    if(count2>nums.length/3) {
    	System.out.println(maj2);
    }

#### *最后感谢yealxxy等人的博客让我更深入的理解了摩尔投票算法,附上[博客传送门][Link 1]* ####

[LeetCode 169_Majority Element]: https://leetcode-cn.com/problems/majority-element/
[LeetCode 229_Majority Element2]: https://leetcode-cn.com/problems/majority-element-ii/
[Link 1]: https://blog.csdn.net/u014248127/article/details/79230221#commentBox