【LeetCode】求众数

题目描述：

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

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

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

解题思路1:

先排序，中间的那个数一定是众数，时间复杂度为O(nlogn);

代码1:

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

解题思路2：

摩尔投票法，时间复制度O(n)；
因为数组中一定存在众数，故众数的个数一定比非众数的个数多，即遇到众数加1，否则减1；

代码2:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int moore = 0;
        for(int num : nums)
        {
            if(count == 0)
                moore = num;
            if(moore == num)
                count++;
            else
                count--;
        }
        return moore;
    }
};

解题思路3:

使用map容器，将数组中的值作为key值，出现的次数作为value值，找出其中众数，时间复杂度为nlog(n);

代码3:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int, int> majorityMap;
        int max=0,maxKey=0;
        for(int num : nums)
        {
            auto it = majorityMap.find(num);
            if(it == majorityMap.end())
                majorityMap.insert(pair<int, int>(num, 1));
            else
                it->second++;
        }
        for(auto it = majorityMap.begin(); it != majorityMap.end(); ++it)
        {
            if(max < it->second)
            {
                max = it->second;
                maxKey = it->first;
            }
        }
        return maxKey;
    }
};

补充知识：STL map关联容器

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。

(1)、map特点：

map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
自动建立Key－value的对应。key 和 value可以是任意你需要的类型。
根据key值快速查找记录，查找的复杂度基本是Log(N)

(2)、基本用法：

1、构造map：map<int, int> mmap;
2、插入数据：以下三种方式等价
mmap.insert(pair<int, int>(1,1));
mmap.insert(map<int, int>::value_type(1,1));
mmap[1] = 1;
3、数据遍历:

for(auto it = mmap.begin(); it != mmap.end(); ++it)
    cout << it->first << " : " << it->second << endl; 

4、按key查找:
auto it = mmap.find(1);//返回key值为1的迭代器
5、删除：
mmap.erase(it);
mmap.erase(1);
mmap.erase(mmap.begin(), mmap.end());