电子商务网站建设与管理的背景,湖北做网站系统哪家好,wordpress中文摘要,做电焊加工的网站剑指 Offer 39. 数组中出现次数超过一半的数字
难度#xff1a;easy\color{Green}{easy}easy 题目描述
数组中有一个数字出现的次数超过数组长度的一半#xff0c;请找出这个数字。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例 1:
输入: …剑指 Offer 39. 数组中出现次数超过一半的数字
难度easy\color{Green}{easy}easy 题目描述
数组中有一个数字出现的次数超过数组长度的一半请找出这个数字。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2限制
1数组长度500001 数组长度 500001数组长度50000
注意本题与主站 169 题相同https://leetcode-cn.com/problems/majority-element/
腾讯视频后端的算法题要求空间复杂度为 O(1)O(1)O(1) 算法
(摩尔投票法)
设输入数组 nums 的众数为 x 数组长度为 n 。 推论一 若记 众数 的票数为 1 非众数 的票数为 −1 则一定有所有数字的 票数和 0 。 推论二 若数组的前 a 个数字的 票数和 0 则 数组剩余 (n−a) 个数字的 票数和一定仍 0 即后 (n−a) 个数字的 众数仍为 x 。
算法流程:
初始化 票数统计 votes 0 众数 x循环 遍历数组 nums 中的每个数字 num 当 票数 votes 等于 0 则假设当前数字 num 是众数当 num x 时票数 votes 自增 1 当 num ! x 时票数 votes 自减 1 返回值 返回 x 即可
复杂度分析 时间复杂度O(n)O(n)O(n)其中 nnn 是数组的长度。 空间复杂度 : O(1)O(1)O(1)只需要 vote 常量
C 代码
class Solution {
public:int majorityElement(vectorint nums) {int vote 0, x 0;for (auto num : nums) {if (vote 0) x num;if (num x) {vote 1;}else {vote - 1;}}return x;}
};
