【编程技巧】精通编程的秘密武器：高效编程技巧揭秘！

🕵️‍♀️1. 摩尔投票算法：求解多数元素

🔍1.1 问题描述：多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素【多数元素是指在数组中出现次数 大于一半及以上的元素】

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2

代码模板：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
    }
};

🔍1.2 摩尔投票算法

摩尔投票算法是一种用于寻找数组中出现次数超过一半的主要元素的高效算法。该算法的核心思想是通过不同元素之间的相互抵消来找到可能的主要元素。

时间复杂度为 O(n)，空间复杂度为 O(1)。

摩尔投票算法的详细步骤：

1. 初始化候选元素和计数器： 选择数组的第一个元素作为候选元素，初始计数器为1。
   
2. 遍历数组：从数组的第二个元素开始遍历，对于每个元素执行以下操作：

• 如果当前元素与候选元素相同，将计数器加1。
• 如果当前元素与候选元素不同，将计数器减1。

• 如果计数器减到0，说明之前的候选元素的出现次数与当前元素的出现次数相抵消，因此选择当前元素作为新的候选元素，并将计数器重新设为1。

摩尔投票算法的关键在于，由于主要元素的出现次数超过一半【前提条件】，其余元素的出现次数总是无法抵消主要元素的出现次数，因此最终剩下的候选元素即为主要元素。

🎉解决代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int num=nums[0],count=0;
        for(int i=0;i<nums.size();i++){
            if(i==0 ||num==nums[i]){
                count++;
            }
            else{
                if(count==0){
                    num=nums[i];
                    count=1;
                }
                else count--;
            }
        }
        return num;
    }
};

参考视频：【摩尔投票法】