一、题目描述

JZ28 数组中出现次数超过一半的数字
题目大意：数组中有一个数字出现的次数超过数组长度的一半, 找出这个数字
注意审题：假设数组是非空的, 故给定的数组中有且只有一个满足条件的数

二、算法1（排序）

解题思路

  1. 我们知道, 对一个数组进行排序之后, 则相同的元素一定是连续的, 因此, 我们可以先对数组从小到大排序, 然后遍历一次排序后的数组, 记录当前数出现的频率, 若出现次数超过数组长度的一半, 则直接返回
  2. 实现细节：由于数组的长度可能是奇数, 因此我们判断时可以把除法转换成乘法

代码实现（C++11）

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        sort(numbers.begin(), numbers.end());    // 从小到大排序
        int x = numbers[0], cnt = 0;    // x 为当前标记的元素, cnt 为x的出现次数
        for(int i = 0; i < n; i++){
            if(numbers[i] == x) ++cnt;    // 当前数等于x
            else x = numbers[i], cnt = 1;    // 否则更新x, cnt置1
            if(2 * cnt > n) return x;    // 判断出现次数是否超过数组长度的一半
        }
        return -1;    // 由于一定有解, 这里随便返回一个数即可
    }
};

时间复杂度：O(nlogn), n是数组的大小, 时间复杂度取决于排序
空间复杂度：O(1), 只使用了几个变量

三、算法2（哈希表）

解题思路

  1. 还有容易想到的办法, 就是记下所有数出现的次数, 因此我们可以使用哈希表这一数据结构来记录
  2. 首先遍历一次数组, 将每个元素出现的次数更新, 更新完后检查一下, 当前更新的元素的出现次数是否大于了数组长度的一半, 是则返回

代码实现（C++11）

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        unordered_map<int, int> freq;    // 创建哈希表

        for(auto & x : numbers){
            ++freq[x];
            if(2 * freq[x] > n) return x;    // 检查条件是否满足
        }

        return -1;
    }
};

时间复杂度：O(n), 哈希表插入和查询的时间复杂度均摊O(1)
空间复杂度：O(n), 哈希表存储所占的空间

四、算法3（摩尔投票法）

解题思路

  1. 对于此类问题有一个经典的求解方法(摩尔投票法), 它的主要思想就是: 一个数的出现次数如果大于数组长度的一半, 那么它和不同于它的其它数相互抵消后, 最后一定还有剩余
  2. 出于这个思想, 我们可以实时记录当前的假定胜者x, 和它的出现次数cnt, cnt为0表示当前没有选出胜者, 这时将当前遍历到的数作为临时胜者即可, 每次当下一个数y != x时, cnt--; 否则 cnt++; 最后的胜者即为x

图片说明

代码实现（C++11）

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        int x, cnt = 0;

        for(int i = 0; i < n; i++){
            if(cnt == 0) x = numbers[i], cnt = 1;    // 选出临时胜者
            else{
                if(numbers[i] != x) --cnt;    // 若y != x
                else ++cnt;        // 若y == x
            }
        }

        return x;
    }
};

时间复杂度：O(n), 遍历一次数组
空间复杂度：O(1), 常数个变量