数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
思路: 哈希
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int>mp;
for(auto it : nums){
mp[it]++;
if(mp[it]>nums.size()/2) return it;
}
return 0;
}
};
时间复杂度: N
空间复杂度: N
更好的思路: 摩尔投票法: 和自己相同的会给自己票数+1, 不相同的会给自己票数-1.
设当前的值可能是众数, 那么遇到下一个不是当前值的时, 统计-1, 并且跳到下下个值. 无论如何, 最终那个众数一定投票统计一定是>0的.
时间复杂度: N
空间复杂度: 1
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 思路: 哈希 时间复杂度: N空间复杂度: N 更...
题目链接： 剑指offer 30-39 目录： 30. 包含 min 函数的栈31. 栈的压入、弹出序列32.1 ...
【剑指offer】Java版代码（完整版） 【剑指offer】1-10题 【剑指offer】11-20题 【剑指o...
剑指 Offer 39. 数组中出现次数超过一半的数字 题目描述： 代码：
1. 来源 剑指offer-面试题39 LeetCode169 https://leetcode.com/prob...
剑指 Offer 39. 数组中出现次数超过一半的数字[https://leetcode.cn/problems/...
title: 每日一练（39）：二进制求和 categories:[剑指offer] tags:[每日一练] da...
剑指offer leetcode
title: 每日一练（47）：找不同 categories:[剑指offer] tags:[每日一练] date...
单例模式 最近在看《剑指offer》，根据《剑指offer》的讲解，结合《effectiveJava》简单学习了一...
本文标题：剑指offer 39 找一个众数
本文链接：https://www.haomeiwen.com/subject/pgijghtx.html
网友评论