2
#yyds干货盘点# leetcode算法题：缺失的第一个正数
source link: https://blog.51cto.com/u_13321676/5433192
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# leetcode算法题：缺失的第一个正数
原创给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
输入：nums = [1,2,0]
输入：nums = [3,4,-1,1]
输入：nums = [7,8,9,11,12]
代码实现：
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}
for (int i = 0; i < n; ++i) {
int num = Math.abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
}
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}
for (int i = 0; i < n; ++i) {
int num = Math.abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
return n + 1;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK