41. First Missing Positive
2650 ワード
class Solution {
public int firstMissingPositive(int[] nums) {
Arrays.sort(nums);
int prev = 0;
if (nums.length < 1) {
return 1;
}
int loc = 0;
while (loc < nums.length && nums[loc] <= 0) {
loc++;
}
while (loc < nums.length) {
if (nums[loc] <= 0) {
loc++;
} else if (nums[loc] == prev + 1) {
loc++;
prev++;
} else if (nums[loc] == prev) {
loc++;
} else {
break;
}
}
return prev + 1;
}
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for First Missing Positive.Memory Usage: 37 MB, less than 27.09% of Java online submissions for First Missing Positive.
あなたも同じ解決策だと信じています^^
sort ==> nlogn
while:nなのでnlognに含めます
Memory: O(1)
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// Base case.
int contains = 0;
for (int i = 0; i < n; i++)
if (nums[i] == 1) {
contains++;
break;
}
if (contains == 0)
return 1;
// nums = [1]
if (n == 1)
return 2;
// Replace negative numbers, zeros,
// and numbers larger than n by 1s.
// After this convertion nums will contain
// only positive numbers.
for (int i = 0; i < n; i++)
if ((nums[i] <= 0) || (nums[i] > n))
nums[i] = 1;
// Use index as a hash key and number sign as a presence detector.
// For example, if nums[1] is negative that means that number `1`
// is present in the array.
// If nums[2] is positive - number 2 is missing.
for (int i = 0; i < n; i++) {
int a = Math.abs(nums[i]);
// If you meet number a in the array - change the sign of a-th element.
// Be careful with duplicates : do it only once.
if (a == n)
nums[0] = - Math.abs(nums[0]);
else
nums[a] = - Math.abs(nums[a]);
}
// Now the index of the first positive number
// is equal to first missing positive.
for (int i = 1; i < n; i++) {
if (nums[i] > 0)
return i;
}
if (nums[0] > 0)
return n;
return n + 1;
}
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for First Missing Positive.Memory Usage: 36.6 MB, less than 75.07% of Java online submissions for First Missing Positive.
Reference
この問題について(41. First Missing Positive), 我々は、より多くの情報をここで見つけました https://velog.io/@jwade/41.-First-Missing-Positiveテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol