当前位置: 首页 > news >正文

169. 多数元素

问题

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:
输入:nums = [3,2,3]
输出:3

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

分析

法一,哈希,找最多出现的元素,或者一边添加哈希一边处理。此外,不需要find,可以直接 ++um[num]。
法二,排序,简单分析可知排序后的nums[n/2]一定是答案。

代码

class Solution {
public:unordered_map<int, int> um;int n = 0;int res = 0;int majorityElement(vector<int>& nums) {n = nums.size();for (int i = 0; i < n; i++) {if (um.find(nums[i]) == um.end()) {um.insert(make_pair(nums[i], 1));} else {um[nums[i]]++;}}int max_count = -1;for (auto it = um.begin(); it != um.end(); it++) {max_count = max(max_count, it->second);}for (auto it = um.begin(); it != um.end(); it++) {if (it->second == max_count) {res = it->first; break;}}return res;}
};

排序

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());return nums[nums.size() / 2];}
};
http://www.hskmm.com/?act=detail&tid=22690

相关文章:

  • Ai元人文:最后的客观与乐观
  • AI元人文:价值原语构想——迈向动态博弈的价值生态
  • 《多分支条件判断优化:switch-case 结构的技术价值分析》
  • Codeforces 1385G Columns Swaps 题解 [ 蓝 ] [ 扩展域并查集 ] [ 二分图最大权匹配 ] [ 基环树建模 ]
  • 72. 编辑距离
  • PlantUML 完整教程:从入门到精通
  • 你妈的
  • test6
  • test7
  • 学习java的第三天
  • vscode github 推送失败
  • 信奥大联赛周赛(提高组)#2515-S 赛后盘点
  • 虚拟机仅主机模式下使用ssh远程连接Linux(EHEL8)连接慢,需要等待30秒以上
  • VLC Player插件和自动激活
  • 第七天
  • logback.xml 常用配置详解 - Higurashi
  • MySQL COUNT(*)性能对比:MyISAM为何比InnoDB快?全面解析与优化方案
  • 2025.10.1总结
  • 子结构判断
  • 使用 Go 进行验证码识别
  • 使用 Rust 进行验证码识别
  • 使用 Swift 进行验证码识别
  • torchtext与torch版本对应关系
  • Python错题集
  • 火狐浏览器新页覆盖旧页解决方法
  • msi主板,windows11,mbr转gpt后,提示0xc000000e1,无法进入系统
  • MAUI下热重载不生效
  • AdGuard广告拦截器APP v4.11.63 / 4.13.7 Nightly 修改版
  • 在疼痛中锚定前路
  • Chrome在Android上Speedometer性能翻倍的技术揭秘