本文最后更新于 406 天前,其中的信息可能已经有所发展或是发生改变。
一、题述
给定一个大小为 n
的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 [n/2]
的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:[3,2,3]
输出:3
示例 2:
输入:[2,2,1,1,1,2,2]
输出:2
进阶:
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
二、题解
1、方法一:排序法
由题意知,我们需要提取出出现次数大于总数一半的“众数”,由数学原理易得,排序后[n/2]
处的数必为我们所需要的那个数。
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(),nums.end());
return nums[nums.size()/2];
}
};
复杂度分析
时间复杂度:数组排序的时间复杂度为O(nlogn)
空间复杂度:O(logn)
2、方法二:哈希表
我们可以采用类似于Python中键值对的方法,对数组进行遍历,收集所有的元素以及他们出现的次数。我们也可以用类似于擂台的办法,保留出现次数最多的数字,以此避免对整个数组的遍历。
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> counts;
int majority = 0, cnt = 0;
for (int num: nums) {
/**
迭代器遍历
,类似于如下代码:
for(int i=0;i<arr.length;i++){
int num = arr[i];
...
}
**/
++counts[num];
if (counts[num] > cnt) {
majority = num;
cnt = counts[num];
}
}
return majority;
}
};
复杂度分析
- 时间复杂度:O(n),
n
是数组nums
的长度.
- 空间复杂度:O(n).
3、方法三:Boyer-Moore 投票算法(Leetcode解法)
有一说一,没太看明白emmm