怎么推广微信公众号_成都网站建站推广_绍兴seo排名_seo是怎么优化

题目描述

给定一个大小为 n 的数组 nums，其中 n 是一个偶数，且数组中的所有数字都在范围 [1, n] 内。数组中存在一个 “主要元素”，其出现次数超过 n/2。找出这个元素。

示例

示例 1:

输入: nums = [3,2,3]
输出: 3

示例 2:

输入: nums = [2,2,1,1,1,2,1,2,2,2,2]
输出: 2

题解

这个问题可以通过使用 Boyer-Moore 投票算法来解决。

1. 初始化：设置两个变量 candidate 和 count，分别用于记录候选的主要元素和它的计数。
2. 第一轮投票：遍历数组，对于每个元素，如果 count 为 0，则将当前元素设置为 candidate，然后 count 加 1；如果当前元素等于 candidate，则 count 加 1；如果不等于，则 count 减 1。
3. 确定主要元素：第一轮结束后，candidate 是主要元素的候选。进行第二轮遍历来验证它是否真的是主要元素。
4. 第二轮验证：遍历数组，统计 candidate 出现的次数，如果出现次数小于 n/2，则不存在主要元素。
5. 返回结果：如果存在主要元素，返回 candidate。

代码实现

int majorityElement(vector<int>& nums) {int candidate = 0, count = 0;for (int num : nums) {if (count == 0) {candidate = num;}count += (num == candidate) ? 1 : -1;}// 验证 candidate 是否是主要元素count = 0;for (int num : nums) {if (num == candidate) count++;}// 如果出现次数大于 n/2，则 candidate 是主要元素return (count > nums.size() / 2) ? candidate : -1;
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历一次数组。
● 空间复杂度：O(1)，因为我们只使用了常数个额外变量。
这个算法的优势在于它的时间效率较高，只需要一次遍历即可找到主要元素，且不需要额外的存储空间。