forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFirst Missing Positive.java
More file actions
59 lines (51 loc) · 1.36 KB
/
First Missing Positive.java
File metadata and controls
59 lines (51 loc) · 1.36 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
Given an unsorted integer array, find the first missing positive integer.
Example
Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Challenge
Your algorithm should run in O(n) time and uses constant space.
Tags Expand
Array
Thoughts:
It means: after it's sorted, what's the first missing postive int counted from 1 ---> more
1. Arrays.sort();
2. count = first non-zero element in A.
3. count +1, and see if maches the current A[i]?
NOTE:
Deal with negative and positive number separately
Watch out for redundant number: ask if the list has duplicated elements
*/
public class Solution {
/**
* @param A: an array of integers
* @return: an integer
*/
public int firstMissingPositive(int[] A) {
if (A == null || A.length == 0) {
return 1;
}
Arrays.sort(A);
int count = -1;
for (int i = 0; i < A.length; i++) {
if (A[i] > 0) {
if (count < 0) {//process 1st positive element
count = A[i];
if (count != 1) {
return 1;
}
}
else if (A[i] == A[i - 1]) {//watch out for duplicates
count--;
}
else if(A[i] != count) {//if not match, kick out
return count;
}
count++;
}
}
if (count < 0) {//if all negative, return 1
return 1;
}
return count;
}
}