数组中重复的数字（简单）

01 Jun 2020 1117字 4分次
BY-SA 4.0（除特别声明或转载文章外）

一、题目描述

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

示例1:

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

限制

2 <= n <= 100000

二、题目解析

遍历数组+哈希表法利用对象中键唯一的特性，对数组进行遍历，如果对象中不存在该键，则设置该键的值为1（这里设置为任意不等于null值均可）。

如果对象中已存在该键，说明当前遍历到的数组元素即为重复的元素，返回即可。
```
 /**
 * @param {number[]} nums
 * @return {number}
 */
 var findRepeatNumber = function(nums) {
     const obj = {};
     for(let num of nums) {
         if(!obj[num]) {
             obj[num] = 1;
         } else {
             return num;
         }
     }
 };
```
- 时间复杂度: O(n)
- 空间复杂度: O(n)

快排+遍历数组法

先用快排对数组进行排序，然后从数组的第二个元素开始遍历，找到等于前一个元素的元素，即为重复的元素, 返回即可。

 /**
 * @param {number[]} nums
 * @return {number}
 */
 var findRepeatNumber = function(nums) {
     nums = quickSort(nums);
     for(let i = 1;i < nums.length;i ++) {
         if(nums[i] === nums[i-1]) {
             return nums[i];
         }
     }
 };

 var quickSort = function(arr) {
     if(arr.length < 2) return arr;
     const left = [];
     const right = [];
     const middleIndex = Math.floor(arr.length / 2);
     const middle = arr[middleIndex];
     for(let i = 0;i < arr.length;i ++) {
         if(i === middleIndex) continue;
         if(arr[i] <= middle) {
             left.push(arr[i]);
         } else {
             right.push(arr[i]);
         }
     }
     return quickSort(left).concat(middle,quickSort(right));
 }

时间复杂度: 即为快排的时间复杂度,O(nlogn)
空间复杂度: O(1)

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

数组中重复的数字（简单） yinshibanxian

一、题目描述

二、题目解析