Duplicate numbers in an array

All numbers in a nums array of length N are in the range 0 to n-1. Some numbers in the array are repeated, but we don’t know how many are repeated, or how many times each number is repeated. Please find any duplicate number in the array.

The following is an example:

/ / input:
[2.3.1.0.2.5.3]
// Output: 2 or 3
Copy the code

Limit :2 <= n <= 100000

Thought analysis

  • Method 1: common solution

We can create a new array and determine whether the new array contains the numS item. If it does not, we add it to the new array. If it does, the item is duplicated. The code is as follows:

    var findRepeatNumber = function(nums) {
        let res = [],repeat = "",len = nums.length,i = 0;
        while(i < len){
            if(res.indexOf(nums[i]) === -1){
                res.push(nums[i]);
            }else{
                // the duplicate number has been found, so the loop is broken
                repeat = nums[i];
                break; }}return repeat;
    }
Copy the code

The time complexity and space complexity of the above algorithms are analyzed as follows:

  • Time complexity O(n).
  • Space complexity O(n).

Method two: in situ replacement algorithm

We try to think so, because the title clearly illustrates the array of the number range is between 0 ~ n – 1 (note that if you don’t have the condition is unable to use this algorithm, this algorithm also just in time in space), that is to say, such as the length of the array is 2, then all the array in the array items can only be 0 or 1, Therefore, we can guess that when the index of the array is equal to the number of the array item, it will not repeat. If it is not equal, then we swap the number of the array item with the number of the array item equal to the number of the array item. In the swap process, when they are equal, it indicates that they are repeated. For example, if [1,1] and [1,1] swap positions, they will always be equal to the array index of 1, which will find the duplicate number.

    var findRepeatNumber = function(nums) {
        for(let i = 0,len = nums.length; i < len; i++){// Define an intermediate variable for exchange
            let temp;
            while(nums[i] ! == i){if(nums[i] === nums[nums[i]]){
                    // Check whether the number of the array item is the same as the number of the array subscript
                    return nums[i];
                }
                // Start swappingtemp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; }}return -1;
    }
Copy the code

The time complexity and space complexity of the above algorithms are analyzed as follows:

  • Time complexity O(n) : The traversal number group uses O(n), and the judgment and exchange operation of each traversal uses O(1).
  • Space complexity O(1) : Extra space with constant complexity.

More questions and solutions can be found here.