8000 refactor 581 · aeonve/Leetcode@c3b120c · GitHub
[go: up one dir, main page]
Skip to content

Commit c3b120c

Browse files
fishercoder1534fishercoder1534
committed
refactor 581 8000 
1 parent cd28e80 commit c3b120c

File tree

2 files changed

+49
-40
lines changed

2 files changed

+49
-40
lines changed

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

Original file line numberDiff line numberDiff line change
@@ -21,47 +21,53 @@
2121
*/
2222
public class _581 {
2323

24-
/**credit: https://discuss.leetcode.com/topic/89282/java-o-n-time-o-1-space
25-
* Use start and end to keep track of the minimum subarray nums[start...end] which must be sorted for the entire array nums.
26-
* If start < end < 0 at the end of the for loop, then the array is already fully sorted.
27-
*
28-
* Time: O(n)
29-
* Space: O(1)*/
30-
public int findUnsortedSubarray(int[] nums) {
31-
int n = nums.length;
32-
int start = -1;
33-
int end = -2;
34-
int min = nums[n - 1];
35-
int max = nums[0];
36-
for (int i = 1; i < n; i++) {
37-
max = Math.max(max, nums[i]);
38-
min = Math.min(min, nums[n - 1 - i]);
39-
if (nums[i] < max) {
40-
end = i;
41-
}
42-
if (nums[n - 1 - i] > min) {
43-
start = n - 1 - i;
24+
public static class Solution1 {
25+
/**
26+
* credit: https://discuss.leetcode.com/topic/89282/java-o-n-time-o-1-space
27+
* Use start and end to keep track of the minimum subarray nums[start...end] which must be sorted for the entire array nums.
28+
* If start < end < 0 at the end of the for loop, then the array is already fully sorted.
29+
*
30+
* Time: O(n)
31+
* Space: O(1)
32+
*/
33+
public int findUnsortedSubarray(int[] nums) {
34+
int n = nums.length;
35+
int start = -1;
36+
int end = -2;
37+
int min = nums[n - 1];
38+
int max = nums[0];
39+
for (int i = 1; i < n; i++) {
40+
max = Math.max(max, nums[i]);
41+
min = Math.min(min, nums[n - 1 - i]);
42+
if (nums[i] < max) {
43+
end = i;
44+
}
45+
if (nums[n - 1 - i] > min) {
46+
start = n - 1 - i;
47+
}
4448
}
49+
return end - start + 1;
4550
}
46-
return end - start + 1;
4751
}
4852

49-
/**
50-
* Time: O(nlogn)
51-
* Space: O(n)
52-
*/
53-
public int findUnsortedSubarray_sorting(int[] nums) {
54-
int[] clones = nums.clone();
55-
Arrays.sort(clones);
56-
int start = nums.length;
57-
int end = 0;
58-
for (int i = 0; i < nums.length; i++) {
59-
if (clones[i] != nums[i]) {
60-
start = Math.min(start, i);
61-
end = Math.max(end, i);
53+
public static class Solution2 {
54+
/**
55+
* Time: O(nlogn)
56+
* Space: O(n)
57+
*/
58+
public int findUnsortedSubarray(int[] nums) {
59+
int[] clones = nums.clone();
60+
Arrays.sort(clones);
61+
int start = nums.length;
62+
int end = 0;
63+
for (int i = 0; i < nums.length; i++) {
64+
if (clones[i] != nums[i]) {
65+
start = Math.min(start, i);
66+
end = Math.max(end, i);
67+
}
6268
}
69+
return (end - start > 0) ? end - start + 1 : 0;
6370
}
64-
return (end - start > 0) ? end - start + 1 : 0;
6571
}
6672

6773
}

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

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -10,24 +10,27 @@
1010
* Created by fishercoder on 5/17/17.
1111
*/
1212
public class _581Test {
13-
private static _581 test;
13+
private static _581.Solution1 solution1;
14+
private static _581.Solution2 solution2;
1415
private static int[] nums;
1516

1617
@BeforeClass
1718
public static void setup() {
18-
test = new _581();
19+
solution1 = new _581.Solution1();
20+
solution2 = new _581.Solution2();
1921
}
2022

2123
@Test
2224
public void test1() {
2325
nums = new int[]{1, 2, 3, 4};
24-
assertEquals(0, test.findUnsortedSubarray(nums));
25-
assertEquals(0, test.findUnsortedSubarray_sorting(nums));
26+
assertEquals(0, solution1.findUnsortedSubarray(nums));
27+
assertEquals(0, solution2.findUnsortedSubarray(nums));
2628
}
2729

2830
@Test
2931
public void test2() {
3032
nums = new int[]{2, 6, 4, 8, 10, 9, 15};
31-
assertEquals(5, test.findUnsortedSubarray(nums));
33+
assertEquals(5, solution1.findUnsortedSubarray(nums));
34+
assertEquals(5, solution2.findUnsortedSubarray(nums));
3235
}
3336
}

0 commit comments

Comments
 (0)
0