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

西南交通建设集团股份有限公司网站厦门网站制作全程服务

西南交通建设集团股份有限公司网站,厦门网站制作全程服务,东莞抖音代运营,建网站公司 深圳LeetCode 169. 多数元素 难度:easy\color{Green}{easy}easy 题目描述 给定一个大小为 nnn 的数组 numsnumsnums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋⌊ n/2 ⌋⌊n/2⌋ 的元素。 你可以假设数组是非空的,并且给…

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

提示:

  • n==nums.lengthn == nums.lengthn==nums.length
  • 1<=n<=5∗1041 <= n <= 5 * 10^{4}1<=n<=5104
  • −109<=nums[i]<=109-10^{9} <= nums[i] <= 10^{9}109<=nums[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(vector<int>& nums) {unordered_map<int, 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

(投票算法)

  1. 定义 cnt 计数器,初始为 0candidate 记录答案。
  2. 从头开始遍历数组,若发现 cnt == 0,则 candidate := nums[i];然后若 candidate == nums[i]cnt++;否则 cnt--
  3. 遍历结束后,若数组中存在主要元素,则主要元素必定是 candidate

复杂度分析

  • 时间复杂度:仅遍历一次数组,故时间复杂度为 O(n)O(n)O(n)

  • 空间复杂度 : 仅使用了两个变量,故需要 O(1)O(1)O(1) 的额外空间。

C++ 代码

class Solution {
public:int majorityElement(vector<int>& 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;}
};
http://www.tj-hxxt.cn/news/111097.html

相关文章:

  • 建设化工网站的目的济南网站优化
  • 成都最专业做网站的网站seo资讯
  • 平台推广销售话术厦门百度整站优化服务
  • 做pcb网站的公司谷歌三件套下载
  • 传媒公司网站设计方案宁德市安全教育平台
  • 北京做建筑信息的网站广告优化
  • wordpress做的网站效果超级软文
  • 外贸网站 流量发稿
  • 福建漳州网站建设费用西安seo网站推广优化
  • 黔东南州两学一做教育网站中级经济师考试
  • 淄博网站建设给力臻动传媒北京seo百度推广
  • 做衣服的网站百度在线咨询
  • wordpress引用js放到最后seo需要培训才能找到工作吗
  • 网站备案 99长沙网络推广哪家
  • 自己建网站做app今日热点新闻排行榜
  • 做免费采集电影网站犯法吗seo怎么做教程
  • 义乌专业做网站的seo网站分析
  • 龙岗微信网站制作百度推广后台登录首页
  • wordpress技术站主题免费seo工具大全
  • 烟台网站制作公司哪家好什么是seo?
  • 做网站数据需求分析35个成功的市场营销策划案例
  • 自己本地可以做网站服务器图片识别搜索引擎
  • 京东网站建设步骤网站建设技术托管
  • asp.net做新闻网站模板网站搭建谷歌seo
  • 德州网站制作哪家好成都关键词优化平台
  • 优就业seo课程学多久长春seo整站优化
  • 来安县城乡建设网站网站信息
  • 做详情页生成代码的网站山东seo网页优化外包
  • 化工材料 技术支持 东莞网站建设下载百度
  • 专业外贸网站建设 诚信 青岛安卓手机优化软件排名