做网站套路,长沙网络工程学院,wordpress 茶业 主题,杭州优化公司排行榜leetcode169. 多数元素
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例 1#xff1a; 输入#xff1a;nums [3,2,3] 输…leetcode169. 多数元素
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1 输入nums [3,2,3] 输出3
示例 2 输入nums [2,2,1,1,1,2,2] 输出2 目录 leetcode169. 多数元素题目分析算法介绍算法证明推论一推论二 算法步骤候选者选择 流程图具体代码算法分析相似题目 题目分析
这道题目要求我们在一个整数数组中找到众数即出现次数超过数组长度一半的元素。题目保证这样的元素必定存在。
注意此题中的众数指的是在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
算法介绍
这里使用的是摩尔投票算法Boyer-Moore Voting Algorithm。这个算法的核心思想是通过相互抵消的方式找到数组中出现次数超过一半的元素。 候选者选择遍历数组维护一个候选元素candidate和计数器count。当count为0时将当前元素设为candidate并将count置为1。如果遇到相同的元素则增加count如果遇到不同的元素则减少count。
算法证明
推论一
假设数组中存在一个众数majority其出现次数为m数组长度为n。由于majority是众数所以m n/2。
对于每个非众数元素我们将其票数记为-1。对于每个众数元素我们将其票数记为1。
由于majority出现的次数超过一半所以所有数字的票数和sum必定大于0。
推论二
假设数组的前a个数字的票数和为0即所有非众数元素已经被抵消。
由于众数majority出现m次其中m n/2所以剩余的n-a个数字中至少还剩下m-a个众数元素。因此剩余数字的票数和仍然大于0即后n-a个数字的众数仍为majority。
算法步骤
候选者选择
遍历数组逐个检查数组中的每个元素。维护候选元素和计数器使用candidate存储当前可能的众数count记录其出现次数。抵消不同元素当遇到与candidate相同的元素时增加count当遇到不同的元素时减少count。当count变为0时更换candidate。
流程图 具体代码
class Solution {
public:int majorityElement(vectorint nums) {int candidate -1;int count 0;for (int num : nums) {if (num candidate)count;else if (--count 0) {candidate num;count 1;}}return candidate;}
};
算法分析
时间复杂度O(n)其中n是数组的长度。算法只需要遍历数组两次。空间复杂度O(1)算法只需要常数级别的额外空间。易错点在维护candidate和count时需要注意逻辑的准确性特别是在count为0时更换candidate。注意点题目已经保证众数存在这是使用摩尔投票算法的前提。
相似题目
题目链接求众数 II在一个整数数组中找到所有出现次数超过 ⌊ n/3 ⌋ 次的元素。检查一个数是否在数组中占绝大多数判断一个数在一个排序数组中是否出现次数超过一半。
