Algorithm: Finger Offer 03. Duplicate number in array

The title

Requirement: Find duplicate numbers in array.

All numbers in an 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.

Example 1:

Input: [2, 3, 1, 0, 2, 5, 3] Output: 2 or 3

Limitations:

2 <= n <= 100000

LeetCode: Offer 03. Duplicate numbers in an array

Their thinking

Method 1: Sort an array

  • Sort the input array
  • Scan the sorted array from beginning to end for duplicate arrays
  • Time: O (nlogn)
  • Space: O(1)

Method two: hash table

  • Each array is scanned sequentially from beginning to end, and each number is scanned sequentially, and each number is scanned sequentially, with an O(1) moment to determine whether the hash contains that number.
  • If the hash table does not have this number, it is added to the hash table. If so, duplicate numbers are found.
  • Time: O (1)
  • Space: O (n)

Method three: compare – exchange

  • Determine whether the corresponding value of I is different from the subscript, if so, the next element. If not, take the value as the subscript m and find the value corresponding to the subscript m.
  • Determine whether the corresponding value of m is equal to the corresponding value of I. If not, the value is switched
  • Until the value of the current I position is equal to the subscript

code

/ * * *@param {number[]} nums
 * @return {number}* /
1. Check whether the value of I is the same as the subscript. If yes, continue. If not, take the value as the subscript m and find the corresponding value of m. * 2. Check whether the value of m subscript is equal to that of I. If not, switch. * * Time: Each digit can be swapped at most twice to find its own position. Total Time: O(n) * Space: no extra Space needs to be allocated. Space: O(1) */

var findRepeatNumber = function(nums) {
    let len = nums.length;
    if(nums == null || len <= 0) {return -1;
    }

    for(let i = 0; i < len; ++i){if(nums[i] < 0 || nums[i] > len - 1) {return false}}const swap = (nums,index1,index2) = > {
        [nums[index1],nums[index2]] = [nums[index2],nums[index1]];
    }

    for(let i = 0; i < len; ++i){
        while(nums[i] ! = i){if(nums[i] == nums[nums[i]]){
                // i.value = m.value
                returnnums[i]; } swap(nums,i,nums[i]); }}return nums[i];
};
Copy the code