面试题 17.10. 主要元素 力扣(简单但不简单) 空间复杂度O(1)

题目描述:

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组,找出其中的主要元素。若没有,返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

示例 1:

输入:[1,2,5,9,5,9,5,5,5]
输出:5

题源:https://leetcode-cn.com/problems/find-majority-element-lcci/

代码:该方法利用Hash,时间复杂度O(N),但是空间复杂度也达到了O(N),不满足

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

法二:要求空间是O(1)

所以只有下面这种方法是可行的:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
    /*  // Hash方法
    int l=nums.size();
    int res=-1;
    map<int ,int>  mp;
    for(int i=0;i<l;i++)
    {
       mp[nums[i]]++;
       if (mp[nums[i]]>l/2) {res=nums[i];  break;}
    }
        return res;
    */
    // 法二,通过题解,投票机制
    int l=nums.size();
    int count=0;  //  对num为众数的投票,如果num众数,则赞成>反对,即count>0
    int num=0;  // 假设现在众数为num
    for(int i=0;i<l;i++)
    {
        if(count==0) {num=nums[i]; count=1; continue;}
        if(nums[i]==num) count++;
           else count--;
    }
    count=0;
    for(int i=0;i<l;i++)
        if(nums[i]==num) count++;
    if (count>l/2) return num;
        else return -1;
        
    }
};

 

面试题 17.10. 主要元素 力扣(简单但不简单) 空间复杂度O(1)

上一篇:圆的面积


下一篇:类的加载过程之 类加载子系统