leetcode-169. 多数元素学习笔记（c++）

写在前面

• 新知识，涨知识，，，
• 学习算法思想
  • 摩尔投票法（Boyer–Moore majority vote algorithm）:
    • 核心思想：对拼消耗
    • 当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。

题目详情

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例 1:
输入: [3,2,3]
输出: 3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

ac代码

class Solution
{
public:
    int majorityElement(vector<int>& nums)
    {
        int cnt = 0;
        int hxuan = -1;
        for(int num : nums)
        {
            if(num == hxuan)
            {
                cnt++;
            }
            else if(--cnt < 0)
            {
                hxuan = num;
                cnt = 1;
            }
        }
        return hxuan;
    }
};

• 注意: 摩尔选票法的直接应用，因为题目说明一定存在大多数，所以不用进行第二阶段
• 算法代码（墙裂推荐）

/*
根据多数元素出现的次数大于n/2且超过其它元素出现次数之和这一特点，进行统计

时间复杂度为：O(n)
空间复杂度为：O(1)
*/
int majorityElement(vector<int>& nums) {
	int k = 0, cand = 0;
	// 步骤1：成对抵销阶阶段
	for(auto num:nums){
		if(k == 0){
			cand = num;
			k = 1;
		}
		else{
			if(num == cand){
				++k;
			}
			else{
				--k;
			}
		}
	}
	// 步骤2：计数阶段 判断cand的个数是否超过一半
	k = 0;
	for(auto num:nums){
		if(num == cand){
			++k;
		}
	}
	if(k <= nums.size() / 2){
		cand = -1;//表示未超过一半 
	}
	return cand;
}
```:
- 文章参考
	- [摩尔投票法(Boyer–Moore majority vote algorithm)](https://blog.csdn.net/happyeveryday62/article/details/104136295)
	- [LeetCode169.多数元素](https://blog.csdn.net/CSDNzhwk/article/details/104833227/)
	- [摩尔投票算法动态演示网站](https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html)