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

做网站老师宁波seo网络推广产品服务

做网站老师,宁波seo网络推广产品服务,竞价推广培训班哪里有,中国万网域名41. 缺失的第一个正数给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 这题要求空间复杂度为O(1),要么定义单个变量,要么原地操作。定义长度为n的数…
41. 缺失的第一个正数给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 

这题要求空间复杂度为O(1),要么定义单个变量,要么原地操作。定义长度为n的数据结构空间复杂度应该是O(n)。我写出来就是空间复杂度O(n)的算法,时间复杂度O(n)。但是能通过… 思路就是用HashSet的contains方法,从1往后看哪个不包含了。
注意,我最开始不是用的set,用的Arrays.asList(newNums).contains(i),这样会超时,换成set就不会超时了。去看了下这两个contains的时间复杂度。

Arrays.asList(...).contains(...): 这是一个链式调用,Arrays.asList 创建一个固定大小的列表,然后 contains 方法在这个列表上进行线性搜索,时间复杂度为 O(n)HashSet.contains 方法的时间复杂度是 O(1)。这意味着在集合中查找元素的时间不会随着集合的大小而增加。在 HashSet 内部,元素是通过计算其哈希码然后存储在基于这个哈希码的位置上的。因此,查找元素时只需要计算该元素的哈希码并查找对应的存储位置即可。如果该位置上有元素且通过 equals 方法比较也匹配,则找到了元素;否则,没有找到元素。
这个特性使得 HashSet.contains 方法能够非常快速地确定元素是否存在于集合中,无论集合中有多少元素。 

我的代码
Arrays.stream(nums).boxed().toArray(Integer[]::new);这一句是为了把int类型转为Integer类型,因为Arrays.asList只能用包装类

这个方法接受一个泛型参数 T,表示数组或者参数的类型。T 必须是一个引用类型,不能是一个基本类型,例如 int, double, char 等。如果传入一个基本类型的数组,Arrays.asList() 会把它当作一个 Object 类型的元素,而不是把它的每个元素当作 Object 类型。这样就会导致返回的 List 只有一个元素,就是原始数组本身。
class Solution {public int firstMissingPositive(int[] nums) {Integer[] newNums = Arrays.stream(nums).boxed().toArray(Integer[]::new);Integer i = 1;Set<Integer> set = new HashSet<>(Arrays.asList(newNums));while (set.contains(i)) {i++;}return i;}
}

官方解法
interesting!有一种手动hash的感觉。
1.把<=0的数改为n+1,这一步就是为了出去非正数,因为他们不影响结果。只需要在正数里面找没出现过的。用这个n+1是因为n个数,里面没出现过的正整数最大只能到n+1,用n+1赋值不影响结果。这里用一个正无穷也是一样的效果。
2.遍历数组中的每一个数x, 将x的绝对值-1作为下标,将这个下标对应的数变成负数(已经是负数就不变)。这一步就是就类似于一个大小为n的数组M,数组M中最大的数为y。那就定义一个大小为y的数组N,然后把M数组中的值-1作为下标散列到数组N中去。然后从前往后遍历,没有被散列到的位置+1就是没出现过的最小的数。
3.按照第2步描述的思想遍历找结果

class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for (int i = 0; i < n; ++i) {if (nums[i] <= 0) {nums[i] = n + 1;}}for (int i = 0; i < n; ++i) {int num = Math.abs(nums[i]);if (num <= n) {nums[num - 1] = -Math.abs(nums[num - 1]);}}for (int i = 0; i < n; ++i) {if (nums[i] > 0) {return i + 1;}}return n + 1;}
}作者:力扣官方题解
链接:https://leetcode.cn/problems/first-missing-positive/solutions/304743/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
http://www.ritt.cn/news/23106.html

相关文章:

  • 新手做淘宝哪个网站比较好免费网站安全软件大全
  • 产品经理兼职做网站报酬长沙靠谱关键词优化公司电话
  • 自己做的网站如何放进服务器免费建自己的网站
  • 网站建设需求调研太原网络营销公司
  • 020网站管理系统模板线上电商怎么做
  • 做软件网站网站内部链接优化方法
  • 网站做描本好处天津快速关键词排名
  • 性价比高的做网站公司关键词查询神器
  • 杭州协会网站建设软件制作
  • java做的网站怎么设置关闭和开启网站访问锦州网站seo
  • 肇庆市建设企业网站怎么样成都高端企业网站建设
  • 公司建网站 内部邮箱链接搜索
  • 哈尔滨制作网站多少钱希爱力双效片骗局
  • 高端定制外贸网站惠州seo收费
  • 做棋牌网站建设哪家好百度识图网页版 在线
  • 成立软件公司百度关键词seo优化
  • 网站推广策划案哪里有免费b站推广网站详情
  • 营销网站建设教程律师推广网站排名
  • 怎么健免费网站吗百度客服中心人工在线咨询
  • 网站建设公司还真有赚钱的seo人员招聘
  • 南宁做网站外包优化网站排名的方法
  • 网站建设公司如何提供客户服务百度联盟
  • 网站建设前期准备方案app怎么开发出来的
  • 怎么用网站做类似微博百度快速收录方法
  • 阜宁网站制作服务商搜索引擎营销的特点包括
  • 个人做同城网站赚钱吗seo推广公司教程
  • 一元云购网站开发网络整合营销方案ppt
  • 温州专业建站网络游戏推广怎么做
  • 建湖做网站的价格网页开发公司
  • 网站建设加优化找竞价托管公司