Repository navigation
Expand file tree
/
Copy pathMissingPositive.java
More file actions
88 lines (69 loc) · 1.67 KB
/
Copy pathMissingPositive.java
File metadata and controls
88 lines (69 loc) · 1.67 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
public class MissingPositive {
public static void main(String[] args) {
MissingPositive x = new MissingPositive();
int[] A = {1,2,3,0,4};
System.out.println(x.firstMissingPositive_v2(A));
}
// DUPLICATES?
/*
* 2,2
* 1
*
* 2,2,3,3,2,2
* 1
*
*/
public int firstMissingPositive_v2(int[] A)
{
if (A.length == 0) return 1;
for (int i = 0; i < A.length; i++) {
if (A[i] <= A.length && A[i] > 0 && A[i] != i+1) {
System.out.println(A[A[i] - 1] + " " + A[i]);
if (A[A[i]-1] != A[i]) { //line 9
int tmp = A[A[i]-1];
A[A[i]-1] = A[i];
A[i] = tmp;
i--; //line 13
}
}
}
for (int i = 0; i < A.length; i++) {
if (A[i] != i+1) return i+1;
System.out.println(A[i] + " " + i);
}
return A.length+1;
}
public int firstMissingPositive(int[] A) {
if(A == null)
return 0;
if(A.length == 0)
return 1;
// 0 1 case || 1
if((A.length == 1 || A[1] == 0) && A[0] == 1)
return A[0] + 1;
// 0 X case
if((A.length == 1 || A[1] == 0)&& A[0] > 1)
return 1;
int max = 0;
int sum = 0;
for(int i = 0; i < A.length; i++)
{
if(A[i] > max)
{
max = A[i];
}
if(A[i] > 0)
sum += A[i];
}
// equation
int posSum = (max * (max - 1));
System.out.println(max + " " + sum + " " + posSum);
//0 1 2 case
if(posSum == 2 && sum == 3)
return 3;
if(sum == posSum)
return max + 1;
// what if need next one
return sum - (posSum/2);
}
}