Commita6583d0

committed

refactor 581

1 parent4b2394d commita6583d0Copy full SHA for a6583d0

File tree

+34

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _581.java
- test/java/com/fishercoder
  - _581Test.java

+34

-0

lines changed

Lines changed: 32 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -34,6 +34,38 @@ public int findUnsortedSubarray(int[] nums) {`
`34`	`34`	`}`
`35`	`35`
`36`	`36`	`publicstaticclassSolution2 {`
	`37`	`+/**`
	`38`	`+ * Time: O(n)`
	`39`	`+ * Space: O(1)`
	`40`	`+ * <p>`
	`41`	`+ * This is just an alternative way of writing Solution1, credit: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/discuss/103057/Java-O(n)-Time-O(1)-Space/106306`
	`42`	`+ *`
	`43`	`+ * But still, initializing end to be -2 is an art to take care of the corner case as in Solution1.`
	`44`	`+ */`
	`45`	`+publicintfindUnsortedSubarray(int[]nums) {`
	`46`	`+intend = -2;`
	`47`	`+intmax =Integer.MIN_VALUE;`
	`48`	`+//go from left to right, find the number that is smaller than the max number on its left side, that should be the end index because it needs to be sorted`
	`49`	`+for (inti =0;i <nums.length;i++) {`
	`50`	`+max =Math.max(max,nums[i]);`
	`51`	`+if (nums[i] <max) {`
	`52`	`+end =i;`
	`53`	`+ }`
	`54`	`+ }`
	`55`	`+intstart = -1;`
	`56`	`+intmin =Integer.MAX_VALUE;`
	`57`	`+//go from right to left, find the number that is bigger than the min number on its right, that should be the beginning index`
	`58`	`+for (inti =nums.length -1;i >=0;i--) {`
	`59`	`+min =Math.min(min,nums[i]);`
	`60`	`+if (nums[i] >min) {`
	`61`	`+start =i;`
	`62`	`+ }`
	`63`	`+ }`
	`64`	`+returnend -start +1;`
	`65`	`+ }`
	`66`	`+ }`
	`67`	`+`
	`68`	`+publicstaticclassSolution3 {`
`37`	`69`	`/**`
`38`	`70`	`* Time: O(nlogn)`
`39`	`71`	`* Space: O(n)`

Lines changed: 2 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -9,12 +9,14 @@`
`9`	`9`	`publicclass_581Test {`
`10`	`10`	`privatestatic_581.Solution1solution1;`
`11`	`11`	`privatestatic_581.Solution2solution2;`
	`12`	`+privatestatic_581.Solution3solution3;`
`12`	`13`	`privatestaticint[]nums;`
`13`	`14`
`14`	`15`	`@BeforeClass`
`15`	`16`	`publicstaticvoidsetup() {`
`16`	`17`	`solution1 =new_581.Solution1();`
`17`	`18`	`solution2 =new_581.Solution2();`
	`19`	`+solution3 =new_581.Solution3();`
`18`	`20`	`}`
`19`	`21`
`20`	`22`	`@Test`

Comments

(0)