题目描述

• 难度：容易
• 找出数组中重复的数字。
• 在一个长度为 n 的数组 nums 里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
• 示例

  输入：
  [2, 3, 1, 0, 2, 5, 3]
  输出：2 或 3 

• 限制：2 <= n <= 100000

思路分析

蛮力算法

• 用两个for循环暴力遍历，比较第i个数字与i后面的数字是否相等，如果相等则找到了一个重复的数字并返回它，不等则i++，直到结束。（i初始为0）。
• 显然，这样将要花费O(n^2)的时间复杂度，O(1)的空间复杂度。这样的时间复杂度实在太高，因此需要想办法去降低时间复杂度。

快排 + 遍历

• 先用快排将数组排序，然后再遍历数组对比第i和第i+1是否相等，如果相等则找到了一个重复的数字并返回，不等则i++，直到结束。（i初始为0）。
• 通过快排来降低时间复杂度，O(nlogn + n) => O(nlogn)（大O表示法），空间复杂度为O(1)。

空间换时间

• 其实看到这道题目时，我最先回想起的是JavaScript中的深克隆的实现方法，可以先通过建立一个空对象（哈希表），然后遍历数组，若此对象（哈希表）没有当前数组元素，则将它添加进对象中，如果存在，则找到了一个重复的数字并返回。
• 通过这样用空间换取时间的方法使得，时间复杂度变为O(n)，而空间复杂度为O(n)。
• 深克隆实现方式

  // *自定义函数实现深克隆
  var obj1 = {
    name: 'moonlightop',
    age: 20,
    sex: 'man',
    card: ['kai','chong']
  }
  var obj2 = {
    name: 'hao',
  }

  function DeepClone (Origin,Target) {
    // 将Origin克隆到Target中(object),返回深克隆好的对象Target
    Target = Target || {};
    // 遍历所有key - value，将它进行分为引用值和原始值
    for (var prop in Origin) {

      if (Origin.hasOwnProperty(prop)) {
        // typeof null -> object，需要排除它
        if (Origin[prop] !== null && typeof(Origin[prop]) === 'object') {
          // array object (typeof)
          if (Object.prototype.toString(Origin[prop]) === '[object object]') {
            // object
            Target[prop] = {};
          } else {
            // array
            Target[prop] = [];
          }
          DeepClone(Origin[prop],Target[prop]);

        } else {
          // number string function boolean null undefined
          Target[prop] = Origin[prop];
        }
      }

    }

    return Target;

  }

  DeepClone(obj1,obj2)
  obj2.card[2] = 'jian'
  console.log(obj2,obj1)

原地置换（一个萝卜一个坑）

• 我本以为已经没有更好的解法了，但一看题解发现，题目中还有一个条件没有使用起来，那就是数组的所有数字都在0～n-1的范围内，结合数组长度为n。
  • 我们完全没有必要新建一个对象或哈希表，直接在原数组中将nums[i]置换到第nums[i]中，通俗点说就是使得萝卜n放置回萝卜坑n中。但如果在将萝卜n放回到萝卜坑n时，发现萝卜坑n已经放有萝卜n，就说明找到了数组的一个重复的数字了。

       1. 初始开始遍历，填好一个坑才前进
           nums[i] 1 2 3 2 萝卜 
              i    0 1 2 3 坑
       2. 发现0号坑中放的是1号萝卜，将它放回1号坑(即nums[i]与nums[nums[i]]交换)
           nums[i] 2 1 3 2 萝卜 
              i    0 1 2 3 坑
       3. 0号坑放的是2号萝卜，同理将它放回2号坑
          nums[i] 3 1 2 2 萝卜 
             i    0 1 2 3 坑
       4. 0号坑放的是3号萝卜，同理将它放回3号坑
       	 nums[i] 2 1 2 3 萝卜 
             i    0 1 2 3 坑
       5. 0号坑放的是2号萝卜，将它放回2号坑时发现坑中已经有了2号萝卜，这样就找到了数组中的出现的重复数字2了
    

  • 这样就可以不需要额外的空间，时间复杂度依然为O(n)来解决这个问题了。

AC代码

/**
 * @param {number[]} nums
 * @return {number}
 */
// 2. 先快速排序，再扫描数组 O(nlogn + n) = O(nlogn) 
// function Divide (low,high,arr) {
//     // console.log(arr,low,arr[low])
//     var ref = arr[low];
//     while (low < high) {
//         while (low < high && arr[high] >= ref) 
//             high --;
//         arr[low] = arr[high];
//         while (low < high && arr[low] <= ref)
//             low ++;
//         arr[high] = arr[low]
//     }
//     arr[low] = ref;
//     return low;
// }

// function Qsort (low,high,arr) {
//     if (low < high) {
//         var divide = Divide(low,high,arr); 
//         Qsort(low,divide - 1,arr);
//         Qsort(divide + 1,high,arr);
//     }
// }


var findRepeatNumber = function(nums) {
    // 1. 暴力解法 O(n^2)
    // for (var i = 0; i < nums.length - 1; i ++) {
    //     for (var j = i + 1; j < nums.length; j ++) {
    //         if (nums[i] === nums[j]) 
    //             return nums[i];
    //     }
    // }

    // 2. 先快速排序，再扫描数组 O(nlogn + n) = O(nlogn) 
    // Qsort (0,nums.length - 1,nums);
    // for (var i = 0; i < nums.length - 1; i ++) {
    //     if (nums[i] === nums[i + 1])
    //         return nums[i];
    // }

    // 3. 用空间换时间，建立一个对象（哈希表），扫描数组，检查当前的数组值是否已经存在数组（哈希表）
    //     O(n)
    // 对象版本
    // var newObj = {};
    // for (var i = 0; i < nums.length; i ++) {
    //     if (newObj.hasOwnProperty(nums[i])) {
    //         return nums[i]
    //     } else {
    //         newObj[ nums[i] ] = nums[i]
    //     }
    // }

    // 4. 扫描数组，使得nums[i] === i，而当nums[i] === nums[ nums[i] ]相等时就存在相同的数字
    //         O(n + k),k是指while循环的次数
    // for (var i = 0; i < nums.length; i ++) {
    //     while (nums[i] !== i) {
    //         if (nums[i] === nums[ nums[i] ]) {
    //             // 返回相同数字
    //             return nums[i];
    //         }
    //         // 交换 nums[i] 与 nums[ nums[i] ]
    //         var j = nums[i];
    //         nums[i] = nums[j];
    //         nums[j] = j;
    //     }
    // }

    var i = 0
    while (i < nums.length) {
        if (nums[i] !== i) {
            if (nums[i] === nums[ nums[i] ]) {
                // 返回相同数字
                return nums[i];
            }
            // 交换 nums[i] 与 nums[ nums[i] ]
            var j = nums[i];
            nums[i] = nums[j];
            nums[j] = j;
        } else {
            i ++
        }
    }

};

总结

• 以前一直没有写题解的习惯，刷完题就算了，经过这一次的回顾，发现自己的题目的解法更加清晰，加深了自己的理解，加油！
• 正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情