目录
算法一：哈希映射
算法思路
- 开一个map容器或者是unordered_map容器来记录一个数出现的次数，最后在逐个访问容器中的元素，找到比
⌊
l
e
n
2
⌋
\lfloor \cfrac{len}{2} \rfloor
⌊2len⌋大的那个就行了
复杂度分析
- 值得注意的是map和unordered_map内嵌数据结构是不同的，map是红黑树，unordered_map是哈希表
使用map
- 时间复杂度，对于map来说是插入、修改、删除操作都是一个
O
(
log
n
)
O(\log n)
O(logn)级别的时间，所以总得时间复杂度是
O
(
n
log
n
)
O(n \log n)
O(nlogn)
- 空间复杂度，map利用率100%,为
O
(
n
)
O(n)
O(n)
使用unordered_map
- 时间复杂度，unordered_map是哈希表，所以每次访问映射后的数是近似
O
(
1
)
O(1)
O(1)的所以总得时间复杂度为
O
(
n
)
O(n)
O(n)
- 空间复杂度，unordered_map的额外，空间复杂度会多出许多，空间利用率约20%，也是
O
(
n
)
O(n)
O(n)级别
- 因为数据可能比较弱，下面两张图片大家自行体会一下map和unordered_map差别
代码实现
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> nums) {
unordered_map<int,int> mp;//key为出现的数字，value为出现的次数
//需要的话，此处只需把unordered_map改成map
for(auto it:nums){//遍历nums中的每一个元素
mp[it]++;//it元素出现的次数+1
}
int len=nums.size();
for(auto it:mp){//遍历map容器中的每一个元素
if(it.second*2>len){//当前数字出现的次数大于数组长度的一半
return it.first;//返回答案
}
}
return 0;//因为编译器原因，必须要有返回值
}
};
算法二：排序
算法思路
- 题目保证有某个数的出现次数超过一半，假如我们将答案排序一遍，最中间的那个数一定是答案，其实不难理解，我们可以看一下图示
- 可以理解为一个长度大于
⌊
l
e
n
2
⌋
\lfloor \cfrac{len}{2} \rfloor
⌊2len⌋的水瓶在长度为
l
e
n
len
len的管道中移动，他必然经过中点
- 严格证明的话，就是反证法，如果存在满足题目条件的数，但是他又不是中点，那么推出来他的长度小于
⌊
l
e
n
2
⌋
\lfloor \cfrac{len}{2} \rfloor
⌊2len⌋，矛盾，故原命题成立
代码实现
C++
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> nums) {
sort(nums.begin(),nums.end());//从小到大排序
return nums[(nums.size()-1)/2];//输出中点
}
};
Python3
class Solution:
def MoreThanHalfNum_Solution(self, nums):
nums.sort()#对列表进行排序
return nums[(len(nums)-1)//2]#输出中点
复杂度分析
- 时间复杂度，排序一遍
O
(
n
log
n
)
O(n \log n)
O(nlogn)
- 空间复杂度，
O
(
1
)
O(1)
O(1)
算法三：性质构造法
算法思路
- 因为题目给定了答案那个数出现的次数大于一半
- 如果我们把这个数字换成1，其余数字换成-1，那么最后整个数组的和肯定是大于0的
- 但是实际上面我们直接换是不可能，因为我们根本不知道那个数是多少
- 但是我们可以先选取一个数字当作临时的也是没有关系的，为什么？
- 上面的想法中1和-1是可以抵消的，如果我们让**-1和-1也可以抵消**呢？那答案不就是更大了！依旧可行！
- 所以我们只需要从头到尾遍历
- 如果cnt为0，就选取当前这个数字为ans，
- 若cnt不为0，则跟ans相同加上，否则减去1
-
这样我们得到的ans，一定是我们的答案（官方题解最后的那个for循环有点冗余，删除掉依旧可以过，当然要理解成官方题解的候选人也是可以的）
代码实现
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> nums) {
int ans,cnt=0;
for(auto it:nums){//遍历nums中的每一个元素
if(!cnt){//如果当前计数为0，则选取当前值为新答案
cnt=1;
ans=it;//更新答案
}
else {
if(ans==it)cnt++;//遇到跟当前答案相同的数
else cnt--;//遇到一个非答案的数
}
}
return ans;//直接返回
}
};
复杂度分析
- 时间复杂度，
O
(
n
)
O(n)
O(n)
- 空间复杂度，定义了ans和cnt，为
O
(
1
)
O(1)
O(1)