主要元素

2021-07-10

面试题 17.10. 主要元素

难度简单165

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

示例 1：

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

示例 2：

1 2	输入：[3,2] 输出：-1

示例 3：

1 2	输入：[2,2,1,1,1,2,2] 输出：2

通过次数62,390

提交次数109,523

摩尔投票

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0;
        int last = -1;
        int n = nums.length;

        for(int i=0;i<n;i++){
            if(nums[i]==last){
                cnt++;
            }else{
                if(cnt>0){
                    cnt--;
                }else{
                    last = nums[i];
                    cnt = 1;
                }
            }
        }
        
        cnt = 0;
        for(int i=0;i<n;i++){
            if(nums[i]==last){
                cnt++;
            }
        }

        if(cnt>n/2){
            return last;
        }else{
            return -1;
        }
        
    }
}

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true