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.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
给一个大小为n的数组,找出它的多数元素。数组非空,多数元素存在。多数元素:出现次数超过n/2的元素(超过数组长度一半)。
解法1: 用两个循环跟踪统计最多次数的元素。 T:O(n*n) S: O(1)
解法2: BST, T:O(nlogn) S: O(n)
解法3:Boyer-Moore多数投票算法 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[] num) { int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}else if(major==num[i]){
count++;
}else count--; }
return major;
}
}
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;
}
};
类似题目:
[LeetCode] 229. Majority Element II 多数元素 II
All LeetCode Questions List 题目汇总