[LeetCode][287. Find the Duplicate Number] 9 Approaches：Brute Force, Count, Hash, In-place Marked, Sorting, Index Sort, Binary Search, Bit Manipulation, Fast Slow Pointers
By Long Luo
This article is the solution 9 Approaches：Brute Force, Count, Hash, In-place Marked, Sorting, Index Sort, Binary Search, Bit Manipulation, Fast Slow Pointers of Problem 287. Find the Duplicate Number.
Here are 9 approaches to solve this problem in Java, which is Brute Force, Count, Hash, In-place Marked, Sorting, Index Sort, Binary Search, Bit Manipulation, Fast Slow Pointers.
Inspired by @user2670f and his solution [C++] 7 Different solutions to this problem (with relaxed constraints) , I added 3 more approaches.
Brute Force (2 Loops)
Since solve the problem without modifying the array nums and uses only constant extra space, we can use Brute Force to solve it.
It’s easy to use 2 loops to do it, but the time complexity is \(O(n^2)\), so it wouldn’t accepted as timeout.1
2
3
4
5
6
7
8
9
10
11
12
13// 2 Loops
public static int findDuplicate_2loops(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
return len;
}
Analysis
- Time Complexity: \(O(n^2)\)
- Space Complexity: \(O(1)\)
Count
Count the frequency of the num in the array.
With extra \(O(n)\) space, without modifying the input.1
2
3
4
5
6
7
8
9
10
11
12public static int findDuplicate(int[] nums) {
int len = nums.length;
int[] cnt = new int[len + 1];
for (int i = 0; i < len; i++) {
cnt[nums[i]]++;
if (cnt[nums[i]] > 1) {
return nums[i];
}
}
return len;
}
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)
Hash
Using a \(\texttt{HashSet}\) to record the occurrence of each number.
With extra \(O(n)\) space, without modifying the input.1
2
3
4
5
6
7
8
9
10
11public static int findDuplicate_set(int[] nums) {
Set<Integer> set = new HashSet<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
if (!set.add(nums[i])) {
return nums[i];
}
}
return len;
}
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)
Marking visited value within the array
Since all values of the array are between \([1 \dots n]\) and the array size is \(n+1\), while scanning the array from left to right, we set the \(\textit{nums}[n]\) to its negative value.
With extra \(O(1)\) space, with modifying the input.1
2
3
4
5
6
7
8
9
10
11
12
13// Visited
public static int findDuplicate_mark(int[] nums) {
int len = nums.length;
for (int num : nums) {
int idx = Math.abs(num);
if (nums[idx] < 0) {
return idx;
}
nums[idx] = -nums[idx];
}
return len;
}
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(1)\)
Sort
Sorting the array first, then use a loop from \(1\) to \(n\).
With extra \(O(nlogn)\) space, modifying the input.1
2
3
4
5
6
7
8
9
10
11public static int findDuplicate_sort(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
for (int i = 1; i < len; i++) {
if (nums[i] == nums[i - 1]) {
return nums[i];
}
}
return len;
}
Analysis
- Time Complexity: \(O(nlogn)\)
- Space Complexity: \(O(logn)\)