面试题 17.10. 主要元素

面试题 17.10. 主要元素

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(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
这一题没什么特别难的地方，我们需要利用一下，这题数据分布的情况
解题代码如下：

int majorityElement(int* nums, int numsSize){
    
    int count=1;
    int x=nums[0];
    int i;
    for(i=1;i<numsSize;i++){
    
        if(count==0){
    
            x=nums[i];
            count++;
            continue;
        }
        if(nums[i]==x){
    
            count++;
        }
        else{
    
            count--;
        }
    }
    count=0;
       for(i=0;i<numsSize;i++){
    
        if(nums[i]==x){
    
            count++;

        }
    }
    if(count>numsSize/2){
    
        return x;
    }
    else{
    
        return -1;
    }

}