来源：力扣（LeetCode）
链接: https://leetcode.cn/problems/majority-element/
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
提示：
- n == nums.length
- 1 <= n <= 5 ∗ 1 0 4 5 * 10^4 5∗104
- − 1 0 9 -10^9 −109 <= nums[i] <= 1 0 9 10^9 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
解法- 哈希表： 哈希表统计出现次数，如果大于半数则返回该元素
- 排序 ： 排序后中间元素肯定是众数
- Boyer-Moore 投票算法：
- 如果 x 与 candidate 相等，那么计数器 count 的值增加 1
- 如果 x 与 candidate 不等，那么计数器 count 的值减少 1
- 分治法： 分两部分，然后比较两部分返回的众数
python实现
class Solution:
def majorityElement(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
counts = dict()
for num in nums:
if num in counts:
counts[num] += 1
else:
counts[num] = 1
if counts[num] > n // 2:
return num
return None
c++实现
class Solution {
public:
int majorityElement(vector& nums) {
int n = nums.size();
if (n == 1) return nums[0];
unordered_map counts;
for(int num: nums) {
auto it = counts.find(num);
if (it != counts.end())
counts[num]++;
else
counts[num] = 1;
if (counts[num] > n/2)
return num;
}
return -1;
}
};
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
python实现
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums)//2]
c++实现
class Solution {
public:
int majorityElement(vector& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
};
复杂度分析
- 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度： O ( l o g n ) O(logn) O(logn)
python实现
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count = 1
item = nums[0]
for num in nums[1:]:
if item == num:
count += 1
else:
count -= 1
if count == 0:
item = num # 变成新的元素
count = 1 # 新的计数
return item
c++实现
class Solution {
public:
int majorityElement(vector& nums) {
int n = nums.size();
if (n == 0)
return nums[0];
int item = nums[0];
int count = 1;
for (int i=1; i
if (nums[i] == item)
count++;
else {
count--;
if (count == 0) {
item = nums[i];
count = 1;
}
}
}
return item;
}
};
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)
python实现
class Solution:
def majorityElement(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
def helper(l, h):
if l == h:
return nums[l]
mid = l + (h-l)//2
left_num = helper(l, mid)
right_num = helper(mid+1, h)
if left_num == right_num:
return left_num
left_count = sum(1 for i in range(l, h+1) if nums[i] == left_num)
right_count = sum(1 for i in range(l, h+1) if nums[i] == right_num)
return left_num if left_count > right_count else right_num
return helper(0, n-1)
c++实现
class Solution {
public:
int helper(vector& nums, int low, int high) {
if (low == high) return nums[low];
int mid = low + (high-low) / 2;
int left_num = helper(nums, low, mid);
int right_num = helper(nums, mid+1, high);
if (left_num == right_num)
return left_num;
int left_count = 0, right_count = 0;
for (int i=0; i
if (nums[i] == left_num)
left_count++;
if (nums[i] == right_num)
right_count++;
}
return left_count > right_count ? left_num : right_num;
}
int majorityElement(vector& nums) {
int n = nums.size();
return helper(nums, 0, n-1);
}
};
复杂度分析
- 时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度： O ( l o g n ) O(logn) O(logn)
- https://leetcode.cn/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
