每日一题，提升自己。今天分享一道关于寻找过半数字的题目，且听我细细道来。

数组 - 寻找过半数字

1. 题目描述

        数组中一定有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

输入：[1, 2, 3, 2, 2, 2, 5, 4, 2]

输出：2

提示：

1 <= 数组长度 <= 50000

2. 解题思路

2.1 思路一

        本题可以用排序法来解决，因为数组中一定有一个数字超过数组长度一半，那么排序之后的数组，中间元素就是要寻找的数字。

复杂度：

• 时间复杂度：O(nlogn)。

2.2 思路二

        本题可以用哈希计数法来解决，在遍历数组的同时，使用当前数字作为key，当前数字出现的次数存为value，存放在一个HashMap中，统计每个数字出现的次数。统计完成之后再遍历一下HashMap，找到value最大的那个值，此时对应的key就是超过数组长度一半的数字。

复杂度：

• 时间复杂度：O(n)。

2.3 思路三

        还有一种方式可以解决本题，那就是摩尔投票，遍历数组，使用count进行计数，记录当前出现的数字为cur，如果遍历到数字与cur相等，则count加一，否则就减一。当count减到0点时候，将cur修改为当前正在遍历的数字，通过增减抵消的方式，最终剩下的数字就是要寻找的过半数字。这种方法相对于前两种来说是最优的。

摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

复杂度：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

3. 算法流程

3.1 思路一流程

排序法：

1. 首先对数组进行排序。
2. 返回排序过后的数组的中间数字。

3.2 思路二流程

哈希计数法：

1. 创建一个HashMap用于存放数据。
2. 遍历数组，判断HashMap中是否存在等于该数字的key。
3. 如果不存在，则将当前数字作为key存入，value等于1。
4. 如果存在，将当前数字对应的value加一。
5. 遍历HashMap，找出最大的value值。
6. 返回value对应的key。

3.3 思路三流程

摩尔投票法：

1. 初始化当前数cur=0，当前计数器count=0。
2. 遍历数组，如果count==0，那么将遍历的当前数赋值给cur，count++。
3. 如果cur等于遍历的当前数，count++。
4. 否则count–。
5. 返回cur。

4. 代码实现

4.1 思路一代码

Java代码实现如下：

1
2
3
4

public static int majorityElement_1(int[] nums){
    Arrays.sort(nums);
    return nums[nums.length / 2];
}

4.2 思路二代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static int majorityElement_2(int[] nums){
    Map<Integer,Integer> map = new HashMap<>();
    for (int num : nums){
        if (map.containsKey(num)){
            map.put(num, map.get(num)+1);
        }else {
            map.put(num, 1);
        }
    }
    Set<Integer> keys = map.keySet();
    int resKey = keys.iterator().next();
    for (Integer key : keys){
        if (map.get(key) > map.get(resKey)){
            resKey = key;
        }
    }
    return resKey;
}

4.3 思路三代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

public static int majorityElement_3(int[] nums){
    int cur=0,count=0;
    for (int i = 0; i < nums.length; i++) {
        if (count == 0) {
            cur = nums[i];
            count++;
        }
        else if (cur == nums[i])
            count++;
        else count--;
    }
    return cur;
}