Find duplicates in an integer array - IDeserve

Find duplicates in an integer array - IDeserve
Given an array of n elements which contains integers from 0 to n-1 only.
The numbers can appear any number of times. Find the repeating numbers.
Example:
Array:  {2, 4, 1, 2, 6, 1, 6, 3, 0}
Output: [1, 2, 6]
Method 1: Naive Solution
Use 2 loops to find duplicates in the array. In outer loop, pick each element one by one and in inner loop check if duplicate exists for that element in the array.
Time Complexity: O(n^2)
Space Complexity: O(1)

Method 2: Use extra space
Since the numbers are in the range 1 to n-1, we can create a count array that will store the count of the numbers in the array.
count[i] represents number of times element i occurs in the array.
In another traversal, find the elements that have count > 1
Time Complexity: O(n)
Space Complexity: O(n)

Method 3:
Traverse the array once and keep reversing the sign of element at array[i]th position.
While traversing, if the sign of array[i]th element is already negative, add it to the duplicates list.
Finally, return duplicates list.
Time Complexity: O(n)
Space Complexity: O(1)

8	public static Set<Integer> getDuplicatesNaive(int[] array) {
9	Set<Integer> duplicates = new HashSet<Integer>();
10	for(int i = 0; i < array.length; i++) {
11	for(int j = i+1; j < array.length; j++) {
12	if(array[i] == array[j]) {
13	duplicates.add(array[i]);
14	}
15	}
16	}
17	return duplicates;
18	}
19
20	public static Set<Integer> getDuplicatesExtraSpace(int[] array) {
21	int n = array.length;
22	Set<Integer> duplicates = new HashSet<Integer>();
23	int[] count = new int[n];
24
25
26	for(int i = 0; i < n; i++) {
27	count[i] = 0;
28	}
29
30
31	for(int i = 0; i < n; i++) {
32	count[array[i]]++;
33	}
34
35
36	for(int i = 0; i < n; i++) {
37	if(count[i] > 1) {
38	duplicates.add(i);
39	}
40	}
41	return duplicates;
42	}
43
44	public static Set<Integer> getDuplicates(int[] array) {
45	int n = array.length;
46	Set<Integer> duplicates = new HashSet<Integer>();
47	for(int i = 0; i < n; i++) {
48
49	if(array[Math.abs(array[i])] > 0) {
50	array[Math.abs(array[i])] = -array[Math.abs(array[i])];
51	} else {
52
53	duplicates.add(Math.abs(array[i]));
54	}
55	}
56	return duplicates;
57	}

Read full article from Find duplicates in an integer array - IDeserve