做网站怎么赚钱的,wordpress+防爬虫,佛山企业网站建设,网络营销seo教程给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1#xff1a;
输入#xff1a;nums [1,2,0]
输出#xff1a;3
解释#xff1a;范围 [1,2] 中的数字都在数组…给你一个未排序的整数数组 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 没有出现。 解题思路
方法一 先使用Arrays.sort()方法排序后使用二分查找时间复杂度O(nlogn)不满足题目要求
方法二 将数组存储到哈希集合中后在遍历确认当前数containsKey()是否存在集合中空间复杂度O(n)不满足题目要求
方法三 将数组当作哈希表存储将每个值存到数组对应位置中如值1存到数组0号索引中值2存到数组1号索引中依次类推若是当前位置的值不是应该对应的值则找到第一个缺失的正数若到最后一个还没找到则数组长度为第一个缺失的值。 解题 由于方法一、方法二不满足题目要求使用方法三解决附上代码
class Solution { /** * 找到数组中第一个缺失的正整数 * * param nums 输入的整数数组 * return 数组中第一个缺失的正整数 */ public int firstMissingPositive(int[] nums) { int len nums.length; // 第一步将所有不在1到len范围内的元素以及重复的元素通过交换到正确的位置来消除重复进行处理 // 这个过程会确保每个位置i0到len-1上的元素要么是nums[i] i 1要么是nums[i] 0或者nums[i] len for (int i 0; i len; i) { //使用while要确保当前位置的值不用移动了可能要移动多次while (nums[i] 0 nums[i] len nums[nums[i] - 1] ! nums[i]) { swap(nums, nums[i] - 1, i); } } // 第二步遍历数组找到第一个不满足nums[i] i 1的位置 // 如果存在这样的位置那么i 1就是第一个缺失的正整数 // 如果遍历完整个数组都没有找到这样的位置说明数组包含了从1到len的所有正整数因此缺失的第一个正整数是len 1 for (int i 0; i len; i) { if (nums[i] ! i 1) { return i 1; } } // 如果数组完整包含了从1到len的所有正整数则返回len 1 return len 1; } /** * 交换数组中两个元素的位置 * * param nums 整数数组 * param a 要交换的第一个元素的索引 * param b 要交换的第二个元素的索引 */ void swap(int[] nums, int a, int b) { int tmp nums[a]; nums[a] nums[b]; nums[b] tmp; }
}
