摩尔投票
摩尔投票：把不同的元素两两抵消，出现次数超过一半的元素最后一定会留下。遍历时维护候选值和它的票数，票数归零就更换候选。
时间复杂度
空间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int majorityElement(int[] nums) {
int cnt = 1;
int ans = nums[0];
for (int i = 1; i < nums.length; ++i) {
if (nums[i] == ans) {
cnt++;
} else if (--cnt == 0) {
ans = nums[i];
cnt = 1;
}
}
return ans;
}
}
|