数组中重复的数字(简单难度)

题目概述(简单难度)

找出数组中重复的数字。

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

示例 1：

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

输出：2 或 3

附上leetcode链接：

点击此处进入leetcode

思路与代码

思路展现

思路1(排序法)

排序法的思路非常的简单，先对数组进行排序，假设数组中有重复的数字，那么这两个数字一定是紧挨着的，用一个for循环进行比较即可，如果相等就返回nums[i]，否则返回-1.

代码示例

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(nums[i]==nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }
}

时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。

空间复杂度：O(logn)

思路2(原地交换法，最优解)

这个解法非常的巧妙，首先来看题目，这道题目需要我们仔细的去审题：

题目的前提是在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义：数组元素的 索引 和 值 是 一对多 的关系。

原因是数组的下标取值范围为0~ n-1，所有数字的取值范围也在0~ n-1，假设有重复的数字，说明一个索引值会对应多个数值，这就是一对多的关系

因此，对于这种一对多的关系，可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i] = inums[i]=i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。

下面来看核心思路：

遍历中，第一次遇到数字 x时，将其交换至索引 x 处；而当第二次遇到数字 x 时，一定有 nums[x] = x，此时即可得到一组重复数字。

算法流程：

1

1：遍历数组 nums ，设索引初始值为 i = 0i=0 :

(1):若 nums[i] = inums[i]=i ： 说明此数字已在对应索引位置，无需交换，因此跳过

(2):若 nums[nums[i]] = nums[i],代表索引 nums[i]处和索引 i处的元素值都为 nums[i] ，即找到一组重复值，返回此值 nums[i]

否则： 交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。

2：若遍历完毕尚未返回，则返回 -1。

代码示例

class Solution {
    public int findRepeatNumber(int[] nums) {
       int i=0;
       while(i<nums.length){
           if(nums[i]==i){
               i++;
               continue;
           }
           if(nums[i]==nums[nums[i]]){
               return nums[i];
           }
           int tmp=nums[i];
           nums[i]=nums[tmp];
           nums[tmp]=tmp;
       }
       return -1;
    }
}

算法复杂度分析：

时间复杂度 O(N) ： 遍历数组使用 O(N)，每轮遍历的判断和交换操作使用 O(1) 。

空间复杂度 O(1)： 使用常数复杂度的额外空间。

总结

此算法日常思路是哈希表，最优解可以好好学习下