Commit37d4e34

committed

refactor 442

1 parentb9d92aa commit37d4e34Copy full SHA for 37d4e34

File tree

+41

-2

lines changed

src
- main/java/com/fishercoder/solutions
  - _442.java
- test/java/com/fishercoder
  - _442Test.java

+41

-2

lines changed

Lines changed: 14 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -23,8 +23,20 @@ public List<Integer> findDuplicates(int[] nums) {`
`23`	`23`	`}`
`24`	`24`
`25`	`25`	`publicstaticclassSolution2 {`
`26`		`-//O(1) space`
`27`		`-//O(n) time`
	`26`	`+/**`
	`27`	`+ * O(1) space`
	`28`	`+ * O(n) time`
	`29`	`+ * <p>`
	`30`	`+ * This approach makes full use of what the problem states: all the integers of nums are in the range [1, n],`
	`31`	`+ * this implies that for any value x in this array, x - 1 must be a valid index in this array`
	`32`	`+ * thus, nums[x - 1] is a valid element in this array.`
	`33`	`+ * <p>`
	`34`	`+ * So the solution was born:`
	`35`	`+ * we could mark one element as seen/visited before by negating it,`
	`36`	`+ * so when we encounter this same number again, i.e. the number is negative,`
	`37`	`+ * we know it appeared before, so we add it to the result`
	`38`	`+ * and then negate this number back.`
	`39`	`+ */`
`28`	`40`	`publicList<Integer>findDuplicates(int[]nums) {`
`29`	`41`	`List<Integer>result =newArrayList();`
`30`	`42`	`for (inti =0;i <nums.length;i++) {`

Lines changed: 27 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,27 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.solutions._442;`
	`4`	`+importorg.junit.BeforeClass;`
	`5`	`+importorg.junit.Test;`
	`6`	`+`
	`7`	`+importjava.util.Arrays;`
	`8`	`+`
	`9`	`+importstaticorg.junit.Assert.assertEquals;`
	`10`	`+`
	`11`	`+publicclass_442Test {`
	`12`	`+privatestatic_442.Solution1solution1;`
	`13`	`+privatestatic_442.Solution2solution2;`
	`14`	`+`
	`15`	`+@BeforeClass`
	`16`	`+publicstaticvoidsetup() {`
	`17`	`+solution1 =new_442.Solution1();`
	`18`	`+solution2 =new_442.Solution2();`
	`19`	`+ }`
	`20`	`+`
	`21`	`+@Test`
	`22`	`+publicvoidtest1() {`
	`23`	`+assertEquals(Arrays.asList(2,3),solution1.findDuplicates(newint[]{4,3,2,7,8,2,3,1}));`
	`24`	`+assertEquals(Arrays.asList(2,3),solution2.findDuplicates(newint[]{4,3,2,7,8,2,3,1}));`
	`25`	`+ }`
	`26`	`+`
	`27`	`+}`

Comments

(0)