关于前端:剑指offer刷题之路1数组中重复的数字

题目: 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。

示例如下:

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

限度:2 <= n <= 100000

办法一：一般解法

咱们能够通过创立一个新数组，而后判断新数组当中是否含有 nums 中的数组项，如果没有就增加到新数组中，如果有，则表明数组项反复了，则另外定义一个变量接管这个反复项，而后返回。代码如下:

    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{
                // 代表曾经找到反复数字了，所以跳出循环
                repeat = nums[i];
                break;
            }
        }
        return repeat;
    }

以上算法的工夫复杂度和空间复杂度剖析如下:

工夫复杂度 O(n)。
空间复杂度 O(n)。

办法二: 原地置换算法

咱们尝试如此思考，因为题目很分明的阐明了数组项中的数的范畴是在 0~n-1 之间（留神，如果没有该条件是无奈应用这个算法的，这个算法也只是用工夫换空间而已），也就是说比方数组的长度是 2，那么数组里的所有数组项的数只能是 0 或 1，因而咱们能够猜想当数组下标等于该数组项的数的时候，则肯定不会反复，如果不等于的话，那么咱们把该数组项的数和等于数组下标的数做一个替换地位，在地位的替换过程中，当两者相等了，这就表明反复了。例如[1,1], 两者替换地位始终都会等于 1 所在的数组下标，也就找到反复数字。

    var findRepeatNumber = function(nums) {for(let i = 0,len = nums.length;i < len;i++){
            // 定义一个两头变量用于替换
            let temp;
            while(nums[i] !== i){if(nums[i] === nums[nums[i]]){
                    // 判断数组项对应的数是否和数组数做下标对应的数一样，如果一样则反复
                    return nums[i];
                }
                // 开始做替换
                temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }

以上算法的工夫复杂度和空间复杂度剖析如下:

工夫复杂度 O(n)：遍历数组应用 O(n)，每轮遍历的判断和替换操作应用 O(1)。
空间复杂度 O(1)：应用常数复杂度的额定空间。

更多题以及解法尽在这里。

关于前端:剑指offer刷题之路1数组中重复的数字

数组中反复的数字

思路剖析