跟着专注于计算机视觉的AndyJ的妈妈我学算法之每日一题leetcode面试题17.10. 主要元素

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了跟着专注于计算机视觉的AndyJ的妈妈我学算法之每日一题leetcode面试题17.10. 主要元素，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1710字，纯文字阅读大概需要3分钟。

内容图文

这个题是个基础题，现在c++不熟练，就刷刷简单的题玩玩。
题：

面试题 17.10. 主要元素
数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5
 
示例 2：
输入：[3,2]
输出：-1

示例 3：
输入：[2,2,1,1,1,2,2]
输出：2
 
说明：
你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

这个题太简单，用三种解法解。
code1：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i=0; (i+nums.size()/2)<nums.size();i++){
            if(nums[i]==nums[i+nums.size()/2]){
                return nums[i];
            }
        }
        return -1;
    }
};

直接排序，看一半长度的开始和结束是不是相等。
使用了函数sort()。
好了，
code2：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> hash;
        for(auto x:nums){
            hash[x]++;
            if(hash[x]>(nums.size()/2)){
                return x;
            }
        }
        return -1;
    }
};

使用hash表，学习了hash表的定义。
然后，
代码

for (auto x : nums)

作用就是迭代容器中所有的元素，每一个元素的临时名字就是x，等同于下边代码

for (vector<int>::iterator iter = nums.begin(); iter != nums.end(); iter++)

还有：

 auto可以在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型，类似的关键字还有decltype。

好了，看第三种解法：
code3：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 第三种解法叫摩尔投票法，其实就是互相抵消的那种方法。
        // 只有想清楚逻辑不出错就好，代码比较简单。
        int major=0, cnt=0;
        for(auto x:nums){
            if(cnt==0){
                major = x;
                cnt++;
            }
            else{
                if(major==x)
                    cnt++;
                else
                    cnt--;
            }
        }
        // 判断是不是众数，时间复杂度为2n，也即n
        if(cnt>0){
            int temp=0;
            for(auto x:nums){
                if(major==x)
                    temp++;
            }
            if(temp>(nums.size()/2))
                return major;
            else
                return -1;
        }
        return -1;
    }
};

这种方法叫做摩尔投票法，逻辑简单，直接理顺写下来就好。
好了，就到这里了。
欢迎互相监督讨论学习！

内容总结

以上是互联网集市为您收集整理的跟着专注于计算机视觉的AndyJ的妈妈我学算法之每日一题leetcode面试题17.10. 主要元素全部内容，希望文章能够帮你解决跟着专注于计算机视觉的AndyJ的妈妈我学算法之每日一题leetcode面试题17.10. 主要元素所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---