企业网站建设的总体目标,腾讯云域名续费,网站建设,郴州网红景点排名❓ 剑指 Offer 39. 数组中出现次数超过一半的数字
难度#xff1a;简单
数组中有一个数字出现的次数超过数组长度的一半#xff0c;请找出这个数字。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输…❓ 剑指 Offer 39. 数组中出现次数超过一半的数字
难度简单
数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制
1 数组长度 50000
注意本题 169. 多数元素 相同。
思路投票问题 多数投票问题可以利用 Boyer-Moore Majority Vote Algorithm 来解决这个问题使得时间复杂度为 O ( n ) O(n) O(n)。 使用 cnt 来统计一个元素出现的次数:
当遍历到的元素和统计元素相等时令 cnt否则令 cnt--。如果前面查找了 i 个元素且 cnt 0说明前 i 个元素没有 ans或者有 ans但是出现的次数少于 i / 2 因为如果多于 i / 2 的话 cnt 就一定不会为 0 。此时剩下的 n - i 个元素中ans 的数目依然多于 (n - i) / 2因此继续查找就能找出 ans。
代码(C、Java)
C
class Solution {
public:int majorityElement(vectorint nums) {int ans nums[0], cnt 0;for(int num : nums) {ans cnt 0 ? num : ans;cnt ans num ? cnt : --cnt;}return ans;}
};Java
class Solution {public int majorityElement(int[] nums) {int ans nums[0], cnt 0;for(int num : nums) {ans cnt 0 ? num : ans;cnt ans num ? cnt : --cnt;}return ans;}
}运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中 n 为数组的长度Boyer-Moore 算法只对数组进行了一次遍历。。空间复杂度 O ( 1 ) O(1) O(1)只需要常数级别的额外空间。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
