Given an array of sizen, find the majority element. The majority element is the element that appearsmore than⌊ n/2 ⌋times.
You may assume that the array is non-empty and the majority element always exist in the array.
Credits:
Special thanks to@tsfor adding this problem and creating all test cases.
给一个大小为n的数组,找出它的多数元素。数组非空,多数元素存在。多数元素:出现次数超过n/2的元素(超过数组长度一半)。
解法1: 用两个循环跟踪统计最多次数的元素。 T:O(n*n) S: O(1)
解法2: BST,T:O(nlogn) S: O(n)
解法3:Boyer–Moore majority vote algorithm,T:O(n) S: O(1)
解法4: HashMap,T:O(n) S: O(n)
Java:
public class Solution {
public int majorityElement(int[] nums) {
int res = 0, cnt = 0;
for (int num : nums) {
if (cnt == 0) {res = num; ++cnt;}
else if (num == res) ++cnt;
else --cnt;
}
return res;
}
} Python: T: O(n), S: O(1)
class Solution:
def majorityElement(self, nums):
idx, cnt = 0, 1
for i in xrange(1, len(nums)):
if nums[idx] == nums[i]:
cnt += 1
else:
cnt -= 1
if cnt == 0:
idx = i
cnt = 1
return nums[idx]C++:
class Solution {
public:
int majorityElement(vector<int>& nums) {
int ans = nums[0], cnt = 1;
for (const auto& i : nums) {
if (i == ans) {
++cnt;
} else {
--cnt;
if (cnt == 0) {
ans = i;
cnt = 1;
}
}
}
return ans;
}
};