66import java .util .Set ;
77
88/**
9+ * 442. Find All Duplicates in an Array
10+ *
911 * Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
1012
1113 Find all the elements that appear twice in this array.
@@ -21,31 +23,35 @@ Could you do it without extra space and in O(n) runtime?
2123 */
2224public class _442 {
2325
24- //O(n) space
25- //O(n) time
26- public List <Integer >findDuplicates_solution1 (int []nums ) {
27- Set <Integer >set =new HashSet ();
28- List <Integer >result =new ArrayList ();
29- for (int i :nums ) {
30- if (!set .add (i )) {
31- result .add (i );
26+ public static class Solution1 {
27+ //O(n) space
28+ //O(n) time
29+ public List <Integer >findDuplicates (int []nums ) {
30+ Set <Integer >set =new HashSet ();
31+ List <Integer >result =new ArrayList ();
32+ for (int i :nums ) {
33+ if (!set .add (i )) {
34+ result .add (i );
35+ }
3236 }
37+ return result ;
3338 }
34- return result ;
3539 }
3640
37- //O(1) space
38- //O(n) time
39- public List <Integer >findDuplicates_solution2 (int []nums ) {
40- List <Integer >result =new ArrayList ();
41- for (int i =0 ;i <nums .length ;i ++) {
42- int index =Math .abs (nums [i ]) -1 ;
43- if (nums [index ] <0 ) {
44- result .add (Math .abs (index +1 ));
41+ public static class Solution2 {
42+ //O(1) space
43+ //O(n) time
44+ public List <Integer >findDuplicates (int []nums ) {
45+ List <Integer >result =new ArrayList ();
46+ for (int i =0 ;i <nums .length ;i ++) {
47+ int index =Math .abs (nums [i ]) -1 ;
48+ if (nums [index ] <0 ) {
49+ result .add (Math .abs (index +1 ));
50+ }
51+ nums [index ] = -nums [index ];
4552 }
46- nums [ index ] = - nums [ index ] ;
53+ return result ;
4754 }
48- return result ;
4955 }
5056
5157}