剑指 Offer 39 - 数组中出现次数超过一半的数字
# 📃 题目描述
题目链接:剑指 Offer 39. 数组中出现次数超过一半的数字 (opens new window)
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
# 🔔 解题思路
Boyer-Moore 投票算法:
想象一下,如果把这些数字当做人种,一个数字和另外一个数字打了起来,同归于尽。最后剩下的是不是人数最多的那种人。这里要满足一个条件:某类人的数目一定要大于总人数的一半
算法步骤:我们选择输入数组中第一个元素作为候选元素candidate,并设置其出现次数为count=1。随后遍历数组
- 当遇到与 candidate 相同的元素,count + 1,不同的元素,count - 1
- 当 count 为 0 的时候,选择下一个元素为候选元素,并且置 count= 1
- 遍历到数组的最后,剩下的 candidate 就是要求的结果
class Solution {
public int majorityElement(int[] nums) {
int candidate = nums[0];
// candidate 出现次数
int count = 1;
for (int i = 1; i < nums.length; i ++) {
if (candidate == nums[i]) {
count ++;
}
else {
count --;
}
if (count == 0) {
candidate = nums[i + 1];
}
}
return candidate;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10