[数据结构与算法]面试题17.10. 主要元素

面试题17.10. 主要元素

题目简述：

示例演示

解题思路：

考虑到时间复杂度是O(N)，是常数级别，则需要用到 **摩尔投票法** 原理。

摩尔投票法：
简单理解成两军交战，一打一火拼，最后人数多的一队就赢了
那么在这道题目中，我们也让数组元素“一对一火拼”，谁最后活下来，谁就是这个数组中的个数最多的元素
但是注意！个数最多并不意味着占比超过一半！
因此我们需要算出个数最多的元素一共有多少个，占比超过一半才返回，否则就返回-1

摩尔投票法

int majorityElement(int* nums, int numsSize){
    int candidate=-1;//军队
    int count=0;//军队的人员数量
    
    for(int i=0;i<numsSize;i++)//通过循环找出数组中数量最多的元素，未必占比超过一半
    {  
        if(count==0) candidate=nums[i];//如果count为0，则证明这个军队已经拼完了，得换一个军队啦
        if(candidate!=nums[i]) count--;//如果当前军队不等于candidate，相当于一对一死亡，count--
        else count++;//相同的话是自己人，那就不用一对一啦，直接count++
    }
    
    count=0;//用这个来记住人数最多的军队与的人数是多少
    for(int i=0;i<numsSize;i++)//根据上面找出的人数最多的军队candidate，数出candidate有多少个人
    {
        if(candidate==nums[i]) count++;
    }
    
    return count*2>numsSize?candidate:-1;//计算candidate是否超过占比的一半，如果没有超过就返回-1
}

时间分析：两个循环+常数次其他操作：2N+C，因此时间复杂度是O(N)
空间分析：由于没有开辟新的空间，因此是O(0)

其他方法

当然如果不考虑时间复杂度，可以用其他方法：例如哈希表、双指针搜索，甚至粗暴使用排序然后数数都可以。

具体可以参考LeetCode题解中的解答：四种做法，双指针+排序法+摩尔投票法+哈希表（原谅我没看到复杂度要求）

  																						 By Levi