多数元素

一 问题描述

统计数组中出现次数大于「n/2」的元素，其中n为数组长度，你可以假设该类元素必存在。

[ 169. 多数元素 ]

注意：「n/2」代表对算式 n/2 的结果向下取整，下同。

二 解决方法

1哈希表法

分析

题目要求统计出现次数大于「n/2」的元素，显而易见的方法是：统计所有元素出现的次数，找到其中大于「n/2」的元素。为了方便查找，使用以元素值为键、元素出现次数为值的哈希表作为数据结构。只要构建好哈希表后，目标元素就容易找出来了。

代码

• 初始化以元素为键，以出现次数为值的哈希表

• 遍历数组，将元素存放在哈希表中

• 在遍历过程中，检查是否存在值大于「n/2」的元素，存在则返回该元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> table;
        size_t len = nums.size();
        size_t num = len / 2, ret = 0;
        for (int i = 0; i < len; ++i) {
            if (++table[nums[i]] > num) {
                ret = nums[i];
                break;
            }
        } 
        return ret;
    }
};

• 或者也可以在构建完成哈希表之后，遍历找到值最大的键（次数大于「n/2」肯定是最值），即为所需结果。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> table;
        size_t len = nums.size();
        size_t cnt = 0, ret = nums[0];
        for (int i = 0; i < len; ++i) {
            ++table[nums[i]];
        } 
        for (const auto& item : table) {
            if (item.second > cnt) {
                cnt = item.second;
                ret = item.first;
            }
        } 
        return ret;
    }
};

2 排序法

分析

将数组排序，因为结果元素值出现次数大于「n/2」，考虑最极端情况：结果值最大/最小（起始/终止）且结果值次数为「n/2」+1，其数组下标「n/2」的位置也为该结果值，不管数组大小是奇数还是偶数。

代码

• 给数组排序

• 访问下标「n/2」位置的元素值

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

三 总结

找到数据的特性，解决问题的方法也许很简单。比如方法2中提到排序法，是利用众数的特性，从而让我们可以快速找到目标元素。