设计网站推荐html,网站建设优化公司招聘,如何做网站的关键词排名,wordpress哪些文件需要给777题目描述#xff1a; 给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1#xff1a;
输入#xff1a;nums [1,2,0]
输出#xff1a;3
解释#xff1a;范围 […题目描述 给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
输入nums [1,2,0]
输出3
解释范围 [1,2] 中的数字都在数组中。
示例 2
输入nums [3,4,-1,1]
输出2
解释1 在数组中但 2 没有。
示例 3
输入nums [7,8,9,11,12]
输出1
解释最小的正数 1 没有出现。提示
1 nums.length 105-2^31 nums[i] 2^31 - 1
解题准备 1.了解基本操作既然是找到缺失的第一个正数必然涉及遍历查找其它的暂时看不出来。 2.模拟操作 随便提供可能的数据并得到它们的答案如下图。 人眼很快能得到结果目前看不出步骤。 图1 解题难点1分析 难点1看不出步骤。 既然我们的目标是找到缺失的第一个正数那么朴素的思想是 方案1 定义变量x1对数组元素每次遍历完成遍历后x只要存在x不在数组中那么它就是答案。 对于【123……n】这样的数据最多遍历n*n次即可所以时间复杂度较高约为On^2 方案2 如果说遍历的效率比较低我们可以自然地想到利用Hash表采取空间换时间的思路来优化算法。 简单地说遍历一次数组把数组的元素全部添加进Hash集合HashSet中然后利用其方法查找缺失的正数。 查找的思路和方案1类似都是定义变量x1一遍遍查找只要x不在集合中就是答案。 不过明显地且不说遍历一次数组和遍历一次x一共出现了两次时间复杂度在O(n^2) 就单单说使用Hash集合已经开辟了On的空间复杂度所以还是有问题。 当然效率自然高了很多只是不符合题意罢了。
解题难点2分析 难点2如何优化算法保证其效率的同时又保证其空间复杂度不过高 无所谓先把题目解决了再说即使时间空间复杂度差一些。 其实很多人也能想到既然我们的目标是找到缺失的、最小的正数那么 问题1如果这个数组有序不就很好解决了吗 比如对于有序数组【-2-1012345……n】遍历一遍数组然后找到不相连的两个数中间的数不就是答案吗当然0到第一个正数、一直连续到最后一个数、仅一个数的数组、第一个数就比1大等等特殊情况都值得注意 但是这确实是一个思路。 解决方案也很简单首先排序一遍【排序的时间复杂度可能很高但一般不增加空间复杂度】随后采用遍历方法找到第一个非0的正数D如果没有返回1判断一下D和1的关系如果大于1返回1随后进入循环 判断一下D和下一个数N的关系如果D1N说明二者不相连那么D1就是答案如果相连那么D进一步直到把整个数组遍历完成。 这个算法的时间复杂度大约在ONlogN左右由于在原数组基础上排序所以空间复杂度为O1复杂例子可能过不去但是也是一种思路。
排序代码
class Solution {public int firstMissingPositive(int[] nums) {Arrays.sort(nums); // 排序int L0, R0; // 双指针有助于遍历while(Rnums.length nums[R]0 ){R;}LR; // 指向第一个正数if(Rnums.length){return 1; // 可能没有正数如【-2-1】}if(L0){if(nums[L]!1){return 1; // 可能第一个数就比1大如【789】}}else if(nums[L-1]0 nums[L]1){return 1; // 可能既有负数但是第一个正数就比1大如【-2-156】}if(Rnums.length-1){R; // 保证之后的操作数组不越界}while(Lnums.length){if(nums[L]nums[R]||nums[L]1nums[R]){ // 判断前后是否相连相连有相同、1相等两种形式如【11】【12】L;if(Rnums.length-1){R;}}else{return nums[L]1; // 不相连返回首个正数}}return nums[L-1]1; // 遍历结束全部相连返回正数}
}
解题难点3分析 本题我也是看了答案如果让我做我并不能以题目要求做出来不过提供给我一种新思路 本题特殊思路 一个算法其本质是提供一条路线使输入转变为输出如果从输入无法解决不妨从结果集找思路。 思考“解题难点1分析”中的“方案1”可以发现这种穷举是最本质的做法其它的行为都是在其上做优化。 从结果集入手可以发现对于一个长度为n的数组其缺失的正数只有n1种可能分别是从1到n1。如果是连续的即为n1如【123】该例答案为4。 1.那么我们干脆定义一个辅助数组flag其大小为n 2.然后遍历输入数组nums如果nums【i】满足0并且n因为如果n它一定不是缺失的最小正数就使flag【nums[i]-1】true 3.在遍历结束后再遍历flag只要flag【i】false就说明数组nums中没有这个正数这就是答案。 代码
class Solution {public int firstMissingPositive(int[] nums) {boolean[] datanew boolean[nums.length];// 不初始化的原因是JVM自动把boolean类型的数据置为false。for(int i0; inums.length; i){if(nums[i]nums.lengthnums[i]0){ // 满足两个条件data[nums[i]-1]true;}}for(int i0; inums.length; i){if(!data[i]){return i1; // 返回答案}}// 如果全都是true说明答案是n1return nums.length1;}
}
真正的答案 其实该题要求辅助空间为常数级别所以解题难点3分析中的答案也不符合题意不过已经非常接近了。 由于题目不限制修改数组nums所以可以在数组nums的角度上操作其原理和难点3类似不过思路又更加特别。 1.难点3中flag的作用就是映射将答案映射到第一个false对应的下标上。 2.其实采用一个全为0、大小为n的数组同样满足该目的。 3.不如使其映射到nums上。 难点4怎么做到呢nums中既有正数、又有负数。 步骤 1.负数不影响结果不妨映射到n1上或者0随你也就是遍历nums如果nums【i】0使nums【i】n1或者0。 2.再一次遍历正数如果满足nums【i】n那么使nums【nums[i]-1】0等于0最好判断【错误】 问题2如果nums【i】-1比i更大比如8和1那么遍历到inums【i】-1即8时这个数已经被置0了那怎么处理 所以原数据不能乱变起码要使得后来的操作可以处理。 3.删除2同样的思路使nums【nums[i]-1】 - nums【nums[i]-1】这保证了可以通过绝对值获得数据。这也是最难的一步 4.最后遍历一遍数组和遍历boolean数组一样找到第一个非负boolean中是false的数这个数下标1就是答案。 5.如果全都小于等于0说明答案是n1。
代码不在此发布因为不是我写的。
以上内容即我想分享的关于力扣热题10的一些知识。 我是蚊子码农如有补充欢迎在评论区留言。个人也是初学者知识体系可能没有那么完善希望各位多多指正谢谢大家。
