LeetCode热题100--169. 多数元素--简单

题目

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

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

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

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

题解

classSolution{publicintmajorityElement(int[]nums){intx=0,votes=0;for(intnum:nums){if(votes==0)x=num;votes+=num==x?1:-1;}returnx;}}

解析

出自：169. 多数元素（摩尔投票，清晰图解）

classSolution{publicintmajorityElement(int[]nums){// 初始化候选众数 x（当前假设的多数元素）// votes 表示当前候选者的“净票数”（支持票 - 反对票）intx=0,votes=0;// 遍历数组中的每一个数字 numfor(intnum:nums){// 如果当前票数为 0，说明之前的候选者已被完全抵消，// 此时选择当前 num 作为新的候选众数if(votes==0)x=num;// 更新票数：// - 如果当前数字 num 等于当前候选者 x，则票数 +1（获得一票）// - 否则，票数 -1（被一个不同元素抵消一票）// 利用三元运算符：num == x ? 1 : -1votes+=num==x?1:-1;}// 由于题目保证存在“多数元素”（出现次数 > n/2），// 最终剩下的候选者 x 必然是真正的众数，直接返回即可returnx;}}