法1:摩尔投票
相同题目:剑指:过半元素
Python
class Solution:
def majorityElement(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
vote = 1
res = nums[0]
n = len(nums)
for i in range(1, n):
if nums[i] == res:
vote += 1
else:
vote -= 1
if vote == 0:
res = nums[i]
vote = 1
return res
Java
class Solution {
public int majorityElement(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int vote = 1, res = nums[0];
for (int i = 1; i < nums.length; ++i) {
if (nums[i] == res) {
++vote;
} else {
--vote;
if (vote == 0) {
res = nums[i];
vote = 1;
}
}
}
return res;
}
}
// 简化代码
class Solution {
public int majorityElement(int[] nums) {
int vote = 0, res = 0;
for (int i = 0; i < nums.length; ++i) {
res = vote == 0 ? nums[i] : res;
vote += res == nums[i] ? 1 : -1;
}
return res;
}
}