题目描述

Given an array of size n, find the majority element. The majority element is the element that appears more than `⌊ n/2 ⌋` times.

You may assume that the array is non-empty and the majority element always exist in the array.

解法一

思路

``````1   2
1   3
1   4
1   5
1   2
------
1``````

``````i = 0           count_1 = 0 -> 1
i = 1           count_1 = 1 -> 2
i = 2   1   2   count_1 = 2 -> 1
i = 3   1   3   count_1 = 1 -> 0
i = 4           count_1 = 0
i = 5   4   5   count_1 = 0
i = 6           count_1 = 0 -> 1
i = 7           count_1 = 0 -> 2
i = 8   1   2   count_1 = 2 -> 1
i = 9           count_1 = 1 -> 2
i = 10          count_1 = 2 -> 3

output: 1``````

Python

``````class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
majority = None
count = 0
for num in nums:
if count == 0:
majority = num
if majority == num:
count += 1
else:
count -= 1
return majority``````

Java

``````public class Solution {
public int majorityElement(int[] nums) {
int majority = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
majority = num;
}
if (majority == num) {
count++;
} else {
count--;
}
}
return majority;
}
}``````

C++

``````class Solution {
public:
int majorityElement(vector<int> &nums) {
int majority = 0;
int count = 0;
for (int &num : nums) {
if (count == 0) {
majority = num;
}
if (majority == num) {
count++;
} else {
count--;
}
}
return majority;
}
};``````