刷题之旅从数组类型的题目开始。第十三道题目是多数元素，对应leetcode的题号为169。

image

题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

1
2
输入: [3,2,3]
输出: 3

示例 2:

1
2
输入: [2,2,1,1,1,2,2]
输出: 2

解题思路

题目提示说一定存在那个多数的数，因此我们不要想其他复杂的情形了，只要专注于找这个数即可。第一个想到的思路是用MAP来存储元素和元素出现的个数，一旦某个元素的个数达标就返回结果，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;
class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length == 0 || nums == null){
            return 0;
        }
        //只有一个元素的时候，直接返回第一个元素即可
        if(nums.length == 1){
            return nums[0];
        }
        //用map存储，key存储nums[i]，value存储个数，逐一比较的过程中判断哪个元素个数大于一半就返回
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
                if(map.get(nums[i]) > nums.length/2){
                    return nums[i];
                }
            }else{
                map.put(nums[i],1);
            }
        }
        //走到这里说明找不到，不过按照题意，是一定可以找到的
        return -1;
    }
}

不过发现时间复杂度比较高：

1
2
执行用时 :27 ms, 在所有 Java 提交中击败了15.28%的用户
内存消耗 :39.8 MB, 在所有 Java 提交中击败了93.22%的用户

经过翻答案，发现了一个比较好的方法，那就是大名鼎鼎的摩尔投票法，基本思想为：我们假设这样一个场景，在一个游戏中，分了若干个队伍，有一个队伍的人数超过了半数。所有人的战力都相同，不同队伍的两个人遇到就是同归于尽，同一个队伍的人遇到当然互不伤害。这样经过充分时间的游戏后，最后的结果是确定的，一定是超过半数的那个队伍留在了最后。

其实一样，经过这种抵消计数，最终能留下来的一定就是数量大于一半的数字了，效果的提升也很明显：

1
2
执行用时 :2 ms, 在所有 Java 提交中击败了87.08%的用户
内存消耗 :43 MB, 在所有 Java 提交中击败了81.15%的用户

代码见下面。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int majorityElement(int[] nums) {
        //count专门来计数
        int count = 0;
        //res作为对比的数
        int res = 0;
        for(int i=0;i<nums.length;i++){
            //count为0说明前面都抵消了，前面的已经没有对比价值了，重新开始继续比
            if(count == 0){
                res = nums[i];
                count = 1;
            }else{
                if(nums[i] == res){
                    count++;
                }else{
                    count--;
                }
            }
        }
        return res;
    }
}

其实还可以通过排序来做，排完序后，数量大于一半的数字，一定会出现在数组的中间位置。