Skip to content

Commit 427ad19

Browse files
fishercoder1534fishercoder1534
committed
refactor 922
1 parent 4e555a3 commit 427ad19

File tree

2 files changed

+128
-14
lines changed

2 files changed

+128
-14
lines changed

‎src/main/java/com/fishercoder/solutions/_922.java

Lines changed: 78 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,93 @@
11
package com.fishercoder.solutions;
22

3+
import java.util.ArrayList;
4+
import java.util.List;
5+
36
public class _922 {
47
public static class Solution1 {
5-
public int[] sortArrayByParityII(int[] A) {
6-
for (int i = 0, j = 1; i < A.length - 1 && j < A.length; ) {
7-
if (A[i] % 2 != 0 && A[j] % 2 == 0) {
8-
int tmp = A[i];
9-
A[i] = A[j];
10-
A[j] = tmp;
8+
/**
9+
* Space: O(n)
10+
* Time: O(n)
11+
*/
12+
public int[] sortArrayByParityII(int[] nums) {
13+
List<Integer> odds = new ArrayList<>();
14+
List<Integer> evens = new ArrayList<>();
15+
for (int i = 0; i < nums.length; i++) {
16+
if (nums[i] % 2 == 0) {
17+
evens.add(nums[i]);
18+
} else {
19+
odds.add(nums[i]);
20+
}
21+
}
22+
int oddIndex = 0;
23+
int evenIndex = 0;
24+
for (int i = 0; i < nums.length; i++) {
25+
if (i % 2 == 0) {
26+
nums[i] = evens.get(evenIndex++);
27+
} else {
28+
nums[i] = odds.get(oddIndex++);
29+
}
30+
}
31+
return nums;
32+
}
33+
}
34+
35+
public static class Solution2 {
36+
/**
37+
* Space: O(1)
38+
* Time: O(n^2)
39+
*/
40+
public int[] sortArrayByParityII(int[] nums) {
41+
for (int i = 0; i < nums.length; i++) {
42+
if (i % 2 == 0 && nums[i] % 2 != 0) {
43+
for (int j = i + 1; j < nums.length; j++) {
44+
if (j % 2 != 0 && nums[j] % 2 == 0) {
45+
int tmp = nums[j];
46+
nums[j] = nums[i];
47+
nums[i] = tmp;
48+
break;
49+
}
50+
}
51+
} else if (i % 2 != 0 && nums[i] % 2 == 0) {
52+
for (int j = i + 1; j < nums.length; j++) {
53+
if (j % 2 == 0 && nums[j] % 2 != 0) {
54+
int tmp = nums[j];
55+
nums[j] = nums[i];
56+
nums[i] = tmp;
57+
break;
58+
}
59+
}
60+
}
61+
}
62+
return nums;
63+
}
64+
}
65+
66+
public static class Solution3 {
67+
/**
68+
* This is the most efficient solution: one implicit condition is that:
69+
* we start with index zero for i, so we look for nums[i] that is not an even number to be swapped with;
70+
* we start with index one for j, so we look for nums[j] that is not an odd number to be swapped with.
71+
* Time: O(n)
72+
* Space: O(1)
73+
*/
74+
public int[] sortArrayByParityII(int[] nums) {
75+
for (int i = 0, j = 1; i < nums.length - 1 && j < nums.length; ) {
76+
if (nums[i] % 2 != 0 && nums[j] % 2 == 0) {
77+
int tmp = nums[i];
78+
nums[i] = nums[j];
79+
nums[j] = tmp;
1180
i += 2;
1281
j += 2;
1382
}
14-
while (i < A.length - 1 && A[i] % 2 == 0) {
83+
while (i < nums.length - 1 && nums[i] % 2 == 0) {
1584
i += 2;
1685
}
17-
while (j < A.length && A[j] % 2 != 0) {
86+
while (j < nums.length && nums[j] % 2 != 0) {
1887
j += 2;
1988
}
2089
}
21-
return A;
90+
return nums;
2291
}
2392
}
2493
}

‎src/test/java/com/fishercoder/_922Test.java

Lines changed: 50 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -7,25 +7,70 @@
77

88
public class _922Test {
99
private static _922.Solution1 solution1;
10-
private static int[] A;
10+
private static _922.Solution2 solution2;
11+
private static _922.Solution3 solution3;
12+
private static int[] nums;
1113
private static int[] result;
1214

1315
@BeforeClass
1416
public static void setup() {
1517
solution1 = new _922.Solution1();
18+
solution2 = new _922.Solution2();
19+
solution3 = new _922.Solution3();
1620
}
1721

1822
@Test
1923
public void test1() {
20-
A = new int[]{4, 2, 5, 7};
21-
result = solution1.sortArrayByParityII(A);
24+
nums = new int[]{4, 2, 5, 7};
25+
result = solution1.sortArrayByParityII(nums);
26+
CommonUtils.printArray(result);
27+
result = solution2.sortArrayByParityII(nums);
28+
CommonUtils.printArray(result);
29+
result = solution3.sortArrayByParityII(nums);
2230
CommonUtils.printArray(result);
2331
}
2432

2533
@Test
2634
public void test2() {
27-
A = new int[]{3, 1, 4, 2};
28-
result = solution1.sortArrayByParityII(A);
35+
nums = new int[]{3, 1, 4, 2};
36+
result = solution1.sortArrayByParityII(nums);
37+
CommonUtils.printArray(result);
38+
result = solution2.sortArrayByParityII(nums);
39+
CommonUtils.printArray(result);
40+
result = solution3.sortArrayByParityII(nums);
41+
CommonUtils.printArray(result);
42+
}
43+
44+
@Test
45+
public void test3() {
46+
nums = new int[]{648, 831, 560, 986, 192, 424, 997, 829, 897, 843};
47+
result = solution1.sortArrayByParityII(nums);
48+
CommonUtils.printArray(result);
49+
result = solution2.sortArrayByParityII(nums);
50+
CommonUtils.printArray(result);
51+
result = solution3.sortArrayByParityII(nums);
52+
CommonUtils.printArray(result);
53+
}
54+
55+
@Test
56+
public void test4() {
57+
nums = new int[]{3, 4};
58+
result = solution1.sortArrayByParityII(nums);
59+
CommonUtils.printArray(result);
60+
result = solution2.sortArrayByParityII(nums);
61+
CommonUtils.printArray(result);
62+
result = solution3.sortArrayByParityII(nums);
63+
CommonUtils.printArray(result);
64+
}
65+
66+
@Test
67+
public void test5() {
68+
nums = new int[]{2, 3, 1, 1, 4, 0, 0, 4, 3, 3};
69+
result = solution1.sortArrayByParityII(nums);
70+
CommonUtils.printArray(result);
71+
result = solution2.sortArrayByParityII(nums);
72+
CommonUtils.printArray(result);
73+
result = solution3.sortArrayByParityII(nums);
2974
CommonUtils.printArray(result);
3075
}
3176
}

0 commit comments

Comments
 (0)