/
045_ReorderNumbers.java
134 lines (109 loc) · 3.52 KB
/
045_ReorderNumbers.java
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
// Coding Interviews: Questions, Analysis & Solutions
// Harry He
public class ReorderNumbers {
//================= Solution 1 =================
public static void reorderOddEven_solution1(int nums[]) {
int begin = 0;
int end = nums.length - 1;
while(begin < end) {
// Move begin forwards until it meets an even number
while(begin < end && (nums[begin] & 0x1) != 0)
begin++;
// Move end backwards until it meets an odd number
while(begin < end && (nums[end] & 0x1) == 0)
end--;
if(begin < end) {
int temp = nums[begin];
nums[begin] = nums[end];
nums[end] = temp;
}
}
}
//================= Solution 2 =================
public static void reorderOddEven_solution2(int nums[]) {
Criterion isEven = new Criterion() {
public boolean check(int num) {
if((num & 0x1) == 0)
return true;
return false;
}
};
reorder(nums, isEven);
}
public interface Criterion{
boolean check(int num);
}
private static void reorder(int nums[], Criterion criterion) {
int begin = 0;
int end = nums.length - 1;
while(begin < end) {
while(begin < end && !criterion.check(nums[begin]))
begin++;
while(begin < end && criterion.check(nums[end]))
end--;
if(begin < end) {
int temp = nums[begin];
nums[begin] = nums[end];
nums[end] = temp;
}
}
}
//================= Test Code =================
private static void test(String testName, int nums[]) {
System.out.print(testName + " begins: ");
int copy[] = new int[nums.length];
for(int i = 0; i < nums.length; ++i)
copy[i] = nums[i];
reorderOddEven_solution1(nums);
if(checkOddBeforeEven(nums))
System.out.print("Solution1 Passed; ");
else
System.out.print("Solution1 FAILED; ");
reorderOddEven_solution2(copy);
if(checkOddBeforeEven(copy))
System.out.print("Solution2 Passed.\n");
else
System.out.print("Solution2 FAILED.\n");
}
private static boolean checkOddBeforeEven(int nums[]) {
int i = 0;
while(i < nums.length) {
if((nums[i] & 0x01) == 0)
break;
++i;
}
while(i < nums.length) {
if((nums[i] & 0x01) == 1)
break;
++i;
}
return (i == nums.length);
}
private static void test1() {
int nums[] = {1, 2, 3, 4, 5, 6, 7};
test("Test1", nums);
}
private static void test2() {
int nums[] = {2, 4, 6, 1, 3, 5, 7};
test("Test2", nums);
}
private static void test3() {
int nums[] = {1, 3, 5, 7, 2, 4, 6};
test("Test3", nums);
}
private static void test4() {
int nums[] = {1};
test("Test4", nums);
}
private static void test5() {
int nums[] = {2};
test("Test5", nums);
}
public static void main(String args[]) {
test1();
test2();
test3();
test4();
test5();
}
}