美文网首页
【LeetCode】求众数

【LeetCode】求众数

作者: MyyyZzz | 来源:发表于2019-04-03 22:37 被阅读0次

    题目描述:

    给定一个大小为 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());

    相关文章

      网友评论

          本文标题:【LeetCode】求众数

          本文链接:https://www.haomeiwen.com/subject/ubitiqtx.html