Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Given an array nums, there is only one number that is repeated, and the number of repeats is unknown. You cannot modify the original array and can only use extra space at the constant level. The time complexity is O(1)O(1)O(1).

Their thinking

Without those restrictions, the question should be reduced to an easy one. Let’s deal with the conditions one by one.

  • unconditional

We can sort the array directly, and then iterate over the array to see if the current element is equal to the next element.

// sort through the loop
public int findDuplicate(int[] nums) {
    Arrays.sort(nums);
    for(int i=0; i<nums.length-1; i++){if(nums[i]==nums[i+1]) return nums[i];
    }
    return -1;
}
Copy the code

The time complexity is O(nlogn)O(nlogn)O(nlogn) O(nlogn) and the space complexity is O(1)O(1)O(1).

  • Cannot modify the original array and the time complexity is O(n)O(n)O(n).

We can use HashSet or HashMap to record values without modifying the array. Here we demonstrate HashMap:

// hash table records
public int findDuplicate(int[] nums) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for(int i=0; i<nums.length; i++){if(map.containsKey(nums[i])){
            return nums[i];
        }else {
            map.put(nums[i], 1); }}return -1;
}
Copy the code
  • Do not modify the original array and the space complexity is O(1)O(1)O(1).

A double loop solves this problem as follows:

// Double loop
public int findDuplicate(int[] nums) {
    for(int i=0; i<nums.length-1; i++){for(int j=i+1; j<nums.length; j++){if(nums[i]==nums[j]) returnnums[i]; }}return -1;
}
Copy the code

However, as the time complexity is O(n2)O(n^2)O(n2), it is highly likely that the test will fail.

O(n)O(n)O(n) O(n)O(n)O(n) O(1)O(1)O(1) O(1)O(1)

How fast a pointer

The fast and slow Pointers we’ve used before are used to determine whether a linked list has a loop or not and the input-in loop points. So how to use array as linked list is a problem worth pondering.

Why would you want to make an array a linked list? If we specify the linked list by index, i.e., the value of index 0 is 1, then the successor node of 0 is 1, and nums[1] is 3, so 1 points to 3, and 3 points to 4… Finally, the linked list obtained according to this rule is:

You can see that element 2 is missing, which means that such an array cannot be considered a linked list!

If the array is n+1 and the array elements range from 1 to n, we can’t assume that there are no duplicate elements in the array. For example, an array [1, 3, 4, 2, 2] can be converted to the following linked list according to the same rules:

It can be seen from the linked list that the entry point of the linked list is the repeated element. It can also be proved whether there are repeated elements in the linked list by judging whether there are rings in the linked list. At this point, the problem is changed to the problem of the ring linked list, and the code is as follows:

// The fast or slow pointer entry point is the repeating element
public int findDuplicate(int[] nums) {
    int slow = 0, fast = 0;
    do{
        slow = nums[slow];
        fast = nums[nums[fast]];
    }while(slow! =fast);int index = 0;
    while(index! =slow){ index = nums[index]; slow = nums[slow]; }return slow;
}
Copy the code

Since both the fast and slow Pointers are 0 when we initialize them, we need to take one step first to judge, that is, to use do while. The time complexity of the above code is O(n)O(n)O(n) O(n) and the space complexity is O(1)O(1)O(1) O(1).