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

什么app可以制作价目表seo搜索引擎优化哪家好

什么app可以制作价目表,seo搜索引擎优化哪家好,去哪里找做网站的人,上海火迎网络推广运营优化题目描述: 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1: 输入:nums [1,2,0] 输出:3示例 2: 输…

题目描述:

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1:

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

示例 2:

输入:nums = [3,4,-1,1]
输出:2

示例 3:

输入:nums = [7,8,9,11,12]
输出:1

提示:

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

通过次数

325.7K

提交次数

749K

通过率

43.5%

思路和题解:

设数组长度为n,则确实的第一个正数只能在[1,n+1]的闭区间

思路一:暴力搜索。时间O(n^2),空间O(1),不符合要求

依次判断[1,n]在不在数组里,如果不在就返回那个不在的数,如果都在就返回n+1。代码。

//暴力循环
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n=nums.size();for(int i=1;i<=n;i++){bool flag=false;for(int j=0;j<n;j++){if(nums[j]==i){flag=true;break;}}if(!flag) return i;}return n+1;}
};

思路二:普通的哈希表。时间O(n),空间O(n),不符合要求。

用一个长度为n的数组来标记[1,n]有没有出现过。

//普通哈希表
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n=nums.size();vector<bool> hash(n,false);for(int i=0;i<n;i++){//出现了就标记为真if(nums[i]>0&&nums[i]<=n)hash[nums[i]-1]=true;}for(int i=0;i<n;i++){if(hash[i]==false) return i+1;}return n+1;}
};

思路三:原地哈希表。时间O(n),空间O(1)

思路二是我们能想到的比较好的办法了,但是空间复杂度还是不能达到要求,那我们怎么来优化这个空间复杂度O(n)呢?要知道,只用O(n)的时间复杂度,也就是只用一层的循环,要找出缺失的第一个正数的话,不用其他空间来存储正数存在的状态时不可能的。既然必须要用空间来存储一些状态,又只能额外使用常数的空间,那我们只好拿给定的数组nums作为存储状态的空间。也就是说用原数组nums作为哈希表。

问题是怎么标记一个正数是否出现的状态。对于num<=0&&num>n的数,num在[1,n]之外无论怎么变化,都不会改变答案。那就干脆先把数组里所有<=0的数先变成n+1,之后再遍历数组,把每个[1,n]内的数num对应下标处都改为负数。最后再遍历一遍数组,对应元素不为负就说明这个数对应的位置是第一个缺失的正数。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {//原地哈希表//第一个缺失的数只能出现在[1,n+1]的闭区间里int n=nums.size();for(int i=0;i<n;i++){//若出现负数或零或大于n的数,那第一个确实的数就在[1,n]if(nums[i]<=0) nums[i]=n+1;}for(int i=0;i<n;i++){//将[num-1]标记为负,表示正数num没有缺失,num>n时不用管int num=abs(nums[i]);if(num<=n){nums[num-1]=-abs(nums[num-1]);}}for(int i=0;i<n;i++){if(nums[i]>0) return i+1;}return n+1;}
};

http://www.hengruixuexiao.com/news/31275.html

相关文章:

  • 谈谈网站开发流程北京网站优化方法
  • 镇江建设局网站seo工程师是做什么的
  • 中国建设银行网站-公司机构客户网站如何让百度收录
  • 手机网站的网址是什么原因网络营销的实现方式
  • 金融做市场广告挂哪些网站最新病毒感染什么症状
  • 专业做外贸网站网络营销方案总结
  • 重庆做网站建设公司排名产品市场推广计划书
  • 网站服务器租用价格多少钱一年公司在百度怎么推广
  • 北京国贸网站建设凡科网微信小程序
  • h5个人网站模板网站制作的流程是什么
  • 中国制造网国际站网络广告名词解释
  • 用网站做CAN总线通信好吗seo行业网
  • 南宁做网站优化营销型网站建设模板
  • 企业网站开发毕业报告百度指数有哪些功能
  • 广州官网优化快优吧seo优化
  • 广州十大网站建设鹤壁网络推广哪家好
  • wordpress创建数据库文件湖南seo优化价格
  • 企业营销网站开发建设专家百度广告竞价
  • 自己做网站出证书站长之家ip查询工具
  • 门户型网站建设百度指数下载app
  • 电商论坛网站模板关键词吉他谱
  • 合肥的网站建设州网络营销做得好的品牌
  • 公司网站建设怎么选择wordpress
  • 网站开发技术发展趋势百度关键字优化
  • 宁夏做网站好的公司推广赚钱项目
  • 怀化网站建设搜索引擎优化的实验结果分析
  • 做电商在什么网站吗2021国内最好用免费建站系统
  • ps做网站画布大小是多少电商平台排行榜
  • 做网站需完成的软件全国各城市感染高峰进度查询
  • 西安建站平台seo诊断的网络问题