[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 , so it wouldn’t accepted as timeout.
1 | // 2 Loops |
Analysis
- Time Complexity:
- Space Complexity:
Count
Count the frequency of the num in the array.
With extra space, without modifying the input.
1 | public static int findDuplicate(int[] nums) { |
Analysis
- Time Complexity:
- Space Complexity:
Hash
Using a to record the occurrence of each number.
With extra space, without modifying the input.
1 | public static int findDuplicate_set(int[] nums) { |
Analysis
- Time Complexity:
- Space Complexity:
Marking visited value within the array
Since all values of the array are between and the array size is , while scanning the array from left to right, we set the to its negative value.
With extra space, with modifying the input.
1 | // Visited |
Analysis
- Time Complexity:
- Space Complexity:
Sort
Sorting the array first, then use a loop from to .
With extra space, modifying the input.
1 | public static int findDuplicate_sort(int[] nums) { |
Analysis
- Time Complexity:
- Space Complexity:
Index Sort
If the array is sorted, the value of each array element is its index value , then we can do this:
- If , it means that the order has been sorted, then skip, ;
- If , it means that there is already a value at the correct index, then this value is a duplicated element;
- If none of the above is satisfied, exchange the values of and .
With extra space, with modifying the input.
1 | // Index Sort |
Analysis
- Time Complexity:
- Space Complexity:
Binary Search
Note that the key is to find an integer in the array instead of finding an integer in the input array.
We can use the binary search algorithm, each round we guess one number, then scan the input array, narrow the search range, and finally get the answer.
According to the Pigeonhole Principle, integers, placed in an array of length , at least integer will be repeated.
So guess a number first(the number in the valid range ), count the elements of the array which is less than or equal to in the array.
- If is strictly greater than . According to the Pigeonhole Principle, repeated elements are in the interval ;
- Otherwise, the repeated element is in the interval .
With extra space, without modifying the input.
1 | public static int findDuplicate_bs(int[] nums) { |
Analysis
- Time Complexity:
- Space Complexity:
Bit
This method is convert all the numbers to binary numbers. If we can get each digit of the repeated number in binary, we can rebuild the repeated number.
Count all the bits of and array numbers as respectively, and then restore them bit by bit to get this repeated number.
For example, the th digit, note that in the array, the sum of all the elements whose ith digit is is as convert the number to binary.
As the range , we can also count the sum of the number whose th digit is , we denoted it .
We can easily get that .
The following table lists whether each bit in the binary of each number is or and what the and of the corresponding bit are:
1 | 3 | 4 | 2 | 2 | x | y | |
---|---|---|---|---|---|---|---|
Bit 0 | 1 | 1 | 0 | 0 | 0 | 2 | 2 |
Bit 1 | 1 | 0 | 1 | 1 | 1 | 3 | 2 |
Bit 2 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
From the table, we found that only the th bit , so after bitwise restoration , which is the answer.
The proof of correctness is actually similar to method . We can consider the change of the number of the -th in different example arrays.
-
If appears twice in the test case array, the rest of the numbers appear once, and the th bit of is , then the array x, is exactly one greater than y. If bit of \textit{target} is , then both are equal.
-
If appears three or more times in the array of test cases, then there must be some numbers that are not in the array. At this time, it is equivalent to replacing these with , we consider the impact on when replacing:
-
If the -th bit of the number to be replaced is , and the -th bit of is : remains unchanged, .
-
If the -th bit of the number being replaced is , and the -th bit of is : x plus one, .
-
If the i-th bit of the number to be replaced is , and the -th bit of is : minus one, .
-
If the -th bit of the number to be replaced is , and the -th bit of is : x remains unchanged, satisfying .
-
Therefore, if the ith bit of is , then after each replacement, only will be unchanged or increased. If it is , only will be unchanged or decreased.
When , the ith bit of is , otherwise it is . We only need to restore this repeated number bitwise.
With extra space, without modifying the input.
1 | public static int findDuplicate_bit(int[] nums) { |
Analysis
- Time Complexity:
- Space Complexity:
Fast Slow Pointers
This problem is as same as 142. Linked List Cycle II, you can refer to this solution for the explanation of the slow fast pointer approach to solve this problem.
The key is to understand how to treat the input array as a linked list.
Take the array as an example, the index of this array is , we can map the index to the .
Start from as a new index, and so on, until the index exceeds the bounds. This produces a sequence similar to a linked list.
If there are a repeated numbers in the array, take the array as an example,
Similarly, a linked list is like that:
Here is a cycle, then this linked list can be abstracted as the following figure:
With extra space, without modifying the input.
1 | public int findDuplicate_fastSlow(int[] nums) { |
Analysis
- Time Complexity:
- Space Complexity:
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗