每日一练Day05：寻找多数元素

---

这道题来自LeetCode，下面我们来抽丝剥茧，细品一下解题思想。

多数元素I

题目特点： 大小为n非空数组，并且给定的数组总是存在多数元素、返回其中出现次数大于n/2的元素——多数元素

1、方法一

思路1：
由于给定数组大小为n，所以出现次数大于n/2的元素至多只有一个，如果我们将给定数组排序，那么数组中出现次数超过一半[n/2]的数字，一定是排好序之后，中间位置的数字。

理论成立，实践开始：

public int majorityElement(int[] nums) {
    Arrays.sort(nums);//排序数组
    return nums[nums.length/2];
}
1
2
3
4

测试结果：

2、方法二

思路2：摩尔投票法
首先我们先了解一下摩尔投票法，摩尔投票法主要分为两个阶段即抵消阶段和计数阶段：

抵消阶段： 如果两个不同候选人的投票进行对抗，则抵消掉一张票，如果两个投票相同，则累加抵消次数。如果计票为0，则换候选人，继续重复上述步骤。

计数阶段： 在抵消阶段最后得到的抵消计数只要不为0，那个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数才可确定。

例如找出数组array=[2,3,1,3,3,2,3]中的大于n/2的多数元素，可分解为下述过程：

理论成立，实践开始：

注： 对于这道题，由于题目已经明确说明给定的数组总是存在多数元素，所以可以省去验证步骤。

    public int majorityElement(int[] nums) {
        //初始化候选人和他们的计票
        int count=0;
        int tmp=nums[0];
        for (int i = 0; i < nums.length; i++) {
            //增加抵消次数
            if(nums[i]==tmp) {
                count++;
            } else {
                //抵消一票
                count--;
            }
            //计票数为0，换候选人
            if(count==0) {
                tmp=nums[i+1];
            }
        }
        return tmp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

测试结果：

------------------ （本章完）------------------