那个旅游网站做攻略最好,app模板,美橙网站开发,网络营销案例事件给定一个未排序的整数数组#xff0c;找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3 示例 2:
输入: [3,4,-1,1] 输出: 2 示例 3:
输入: [7,8,9,11,12] 输出: 1 说明:
你的算法的时间复杂度应为O(n)#xff0c;并且只能使用常数级别的空间。
思路找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0] 输出: 3 示例 2:
输入: [3,4,-1,1] 输出: 2 示例 3:
输入: [7,8,9,11,12] 输出: 1 说明:
你的算法的时间复杂度应为O(n)并且只能使用常数级别的空间。
思路把数字放到该放的地方。nums[i]i1
然后检查哪个数不在即可。
class Solution {public int firstMissingPositive(int[] nums) {if(nums null || nums.length 0)return 1;int len nums.length;for (int i 0; i len ; i)while (nums[i] 0 nums[i] len nums[i]!nums[nums[i]-1])swap(nums,i,nums[i]-1);int i 0;while(ilen nums[i] i1)i;return i1;}private void swap(int[] nums,int i, int j){int tmp nums[i];nums[i] nums[j];nums[j] tmp;}
}
