湖北建设注册中心网站,做网站广告多少钱,网站开发项目业务要求,网站文章列表模板LeetCode 169. 多数元素
难度#xff1a;easy\color{Green}{easy}easy 题目描述
给定一个大小为 nnn 的数组 numsnumsnums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋⌊ n/2 ⌋⌊n/2⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给…LeetCode 169. 多数元素
难度easy\color{Green}{easy}easy 题目描述
给定一个大小为 nnn 的数组 numsnumsnums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋⌊ n/2 ⌋⌊n/2⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1
输入nums [3,2,3]
输出3示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
nnums.lengthn nums.lengthnnums.length1n5∗1041 n 5 * 10^{4}1n5∗104−109nums[i]109-10^{9} nums[i] 10^{9}−109nums[i]109
进阶 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。 算法1
(哈希)
使用 C 提供的 unordered_map 记录每个元素出现的次数。 遍历过程在如果次数大于 n/2则返回该数字即可。
复杂度分析 时间复杂度unordered_map 单次插入和查询的时间复杂度为 O(1)O(1)O(1)故总时间复杂度为 O(n)O(n)O(n) 空间复杂度 : 至少需要额外的 O(n)O(n)O(n) 的空间。
C 代码
class Solution {
public:int majorityElement(vectorint nums) {unordered_mapint, int hash;int n nums.size();int res 0;for (int i 0; i n; i ) {hash[nums[i]] ;if (hash[nums[i]] n / 2) res nums[i];}return res;}
};算法2
(投票算法)
定义 cnt 计数器初始为 0candidate 记录答案。从头开始遍历数组若发现 cnt 0则 candidate : nums[i]然后若 candidate nums[i]cnt否则 cnt--。遍历结束后若数组中存在主要元素则主要元素必定是 candidate。
复杂度分析 时间复杂度仅遍历一次数组故时间复杂度为 O(n)O(n)O(n) 空间复杂度 : 仅使用了两个变量故需要 O(1)O(1)O(1) 的额外空间。
C 代码
class Solution {
public:int majorityElement(vectorint nums) {int cnt 0, candidate;for (int i 0; i nums.size(); i ) {if (cnt 0) candidate nums[i];if (nums[i] candidate) cnt ;else cnt --;}return candidate;}
};
