北京seo网站开发,龙岗商城网站建设,莱芜在线论坛莱芜话题西关规划图,seo推广优化公司缺失的第一个正数
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
输入#xff1a;nums [1,2,0]输出#xff1a;3
示例 2
输入#xff1a;nums [3,4,-1,…缺失的第一个正数
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1
输入nums [1,2,0]输出3
示例 2
输入nums [3,4,-1,1]输出2
解题思路
1、题目要求找出未出现的最小正整数因此答案一定在 1 到 n1 的范围内其中 n 是数组的长度。2、我们可以利用数组本身来进行标记将数组的值放到正确的位置上例如如果遍历到数字 3则将其放置到数组索引为 2 的位置上因为数组索引从 0 开始。3、遍历数组 nums将每个元素 nums[i] 放到正确的位置上即 nums[i] 应该放在 nums[nums[i] - 1] 的位置上即i1 num[i]。4、如果 nums[i] 不在 1 到 n 的范围内则忽略它。5、再次遍历数组找出第一个不在正确位置上的元素其索引加 1 就是未出现的最小正整数。
Java实现
public class FirstMissingPositive {public static int firstMissingPositive(int[] nums) {int n nums.length;// 将数组元素放置到正确的位置上for (int i 0; i n; i) {while (nums[i] 0 nums[i] n
// nums[i] ! i 1//特殊条件下出现重复元素时重复元素时nums[i] ! i 1是会死循环的比如{1,1} nums[nums[i] - 1] ! nums[i]) {// 交换 nums[i] 和 nums[nums[i] - 1] 位置上的元素// 即nums[nums[i] - 1]放到到位置i处,nums[i] - 1处的位置腾出来// 把nums[i]放在nums[i] - 1的位置上使得num[i]i1int temp nums[i];nums[i] nums[temp - 1];nums[temp - 1] temp;}}// 找到第一个不满足条件的位置即缺失的最小正整数for (int i 0; i n; i) {if (nums[i] ! i 1) {return i 1;}}// 如果数组中都是正整数且连续则返回 n 1return n 1;}public static void main(String[] args) {int[] nums1 {1, 1};int[] nums2 {3, 4, -1, 1};int result2 firstMissingPositive(nums2);int result1 firstMissingPositive(nums1);System.out.println(result1); // 输出2System.out.println(result2); // 输出2}}
时间空间复杂度
时间复杂度O(n)其中 n 是数组 nums 的长度。空间复杂度O(1)只需要使用常数级别的额外空间
