LeetCode每日一题,2025-9-4

多数元素

投票法

让你找到序列中出现超过二分之一的元素，一定要记住这个规则。
记录两个值val和cnt，刚开始val为任意数，cnt=0。
如果cnt是0，就把当前val = num。接下来判断，ifnum == val，则cnt ++，elsecnt--。最后的val就是出现次数超过二分之一的数。

原理

你可以以‘对冲’思路去想，让你找到出现超过二分之一的数，把这个target当做一只军队，然后剩下的普通num去当做另一只军队，目标数target去跟普通的num去‘对冲’，一换一，最后留下来的肯定是答案。
我上面举得例子是我们上来分出来了哪些是target哪些是普通num，但是代码里怎么分辨呢？其实不用分辨，如果我们看错了target，那么自然会被消耗掉，被消耗掉了会有其他的target顶上，只有真正的target顶上才能完成

class Solution {public int majorityElement(int[] nums) {int n = nums.length;int res = 0;int vote = 0;for(int num:nums){if(vote==0) res = num;if(num == res) vote++;else vote--;}return res;}
}