- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
摩尔投票算法
摩尔投票算法有点“天天爱消除”的感觉，证明过程详见官方题解。
先明确，所谓多数元素就是该元素的个数超过数组长度的一半。
所以我们可以让不同的数字相互抵消，最后剩下的数字就是多数元素。
constmajorityElement=function(nums){lettarget=0letcount=0for(leti=0;i<nums.length;i++){if(count===0){target=nums[i]}if(nums[i]===target){count++}else{count--}}returntarget}
- 时间复杂度: O(n)
- 空间复杂度: O(1)