网站开发官网,北京网站建设专业公司,租用了空间 怎样上传网站程序,浙江省长兴县建设局网站41.给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1#xff1a; 输入#xff1a;nums [1,2,0] 输出#xff1a;3 示例 2#xff1a; 输入#xff1a;nums [… 41.给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1 输入nums [1,2,0] 输出3 示例 2 输入nums [3,4,-1,1] 输出2 示例 3 输入nums [7,8,9,11,12] 输出1 我的想法很简单当该数组排序并去重后再去掉小于等于 0 的部分最终遍历数组时判断是否为从 1 开始连续的数比如 [1,2,3] 那就返回最大值 1 即 4若不为从 1 开始的连续的数组比如 [1,3,4] 中nums[0] 1但是 nums[1] ! 2说明缺失了 2那就直接返回 2 即可。 public int firstMissingPositive(int[] nums) {// 排序Arrays.sort(nums);int i 0;// 从大于 0 处开始遍历相当于去除了小于等于 0 的部分while(inums.length nums[i]0)i;// 从 1 开始往后找看是否为 1,2,3,4...int ans 1;while(inums.length){// 相当于去重while(inums.length - 1 nums[i] nums[i1])i;if(nums[i]!ans)return ans;ans;i;}return ans;}上面也提到了我们的理想数组应该为从 1 开始递增的正整数数组即满足 nums[i] i1 也可以写作 i nums[i]-1所以我们就交换数组元素使得所有能满足的数处于对应的位置。最后从头开始判断是否为理想中的数不是就直接返回如果都满足就返回数组长度 1要处理的还有两个细节1. 排除小于 1 的以及大于数组长度的数2. 排除重复的数第一点好判断主要还是第二点我们可能会写成如果 nums[i]!i1 就交换那交换哪两个数呢我们需要两个下标。所以上面说也可以写作 i nums[i]-1 因为 ab nums[a] nums[b]所以我们判断条件写成 nums[i]nums[nums[i]-1]。而为什么不写作比如 nums[nums[i]]nums[i1] 是因为我们需要判断位置的主体为 nums[i]所以写作 ixxx 的形式这样的写法每次交换位置都会把 nums[i] 放到它应该处于的位置比如 [2,-1,-2] 在第一次遍历会把 nums[0] 也就是 2 换到应该处于的位置即下标为 1 的位置得到 [-1,2,-2]然后继续判断 nums[0] 是否为我们想要的数… public int firstMissingPositive(int[] nums) {int n nums.length;for(int i 0;in;i){// 首先数在理想数组范围// 其次如果 nums[i] 上面的数如果不是 i1 就把它换到正确的位置继续判断换过来的数// 直到 num[i] i 1 就结束这一轮循环while((nums[i]0 nums[i] n) nums[i]!nums[nums[i]-1]){swap(nums,i,nums[i]-1);}}for(int i 0;in;i){if(nums[i]!i1)return i1;}return n1;}public void swap(int[] nums,int i,int j){int temp nums[i];nums[i]nums[j];nums[j]temp;}
