[数据结构与算法]剑指 Offer 03. 数组中重复的数字

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

这道题，可以用的方法很多，可以遍历数组然后用哈希表存放，每次放之前查看是否重复，但哈希表会占用内存空间。而如果先排序再遍历时间复杂度又很高。所以选择下面这种算法，可以保证在空间复杂度O(1)，时间复杂度O(n)。

先上一个例子：

因为数组中的数字都在0～n-1的范围内

若数组中没有重复的数字，那么数字i应该出现在下标为i的位置

若数组中有重复的数字，如果按照下标来分类，那么有些位置可能可能会冲突出现多个数字，而有些位置则会没有数字。

所以我们可以这样做：

从数组nums中下标为0开始遍历

数组排序后，下标为0的位置上对应的数字本应是0

• 若此时不为0，而是m(0<m<n-1)，则将m放回下标为m的位置nums[m],将m位置上原本的数字放在下标为0的位置，然后重复，直到下标为0的位置上元素为0。还有一种情况是可能数组中不存在值为0的元素，但是在找0元素的过程中不断的将各种元素放回自己的位置，如果有两个相同的元素p，下表为0的元素第一次会先判断nums[p]是否等于p，如果nums[p]!=p ，则会与下标为p的位置上的元素交换位置，让下标为p的位置上的元素值为p。第二次再遇到p的时候，会先判断下标为p的位置上的元素值是否为p，发现已经是p，则判定p元素重复。
• 如果下标为x位置上的元素nums[x]是x（nums[x]==x），则继续向后遍历
• 如果有两个相同的元素p，下表为x的元素第一次会先判断nums[p]是否等于p，如果nums[p]!=p ，则会与下标为p的位置上的元素交换位置，让下标为p的位置上的元素值为p。第二次再遇到p的时候，会先判断下标为p的位置上的元素值是否为p，发现已经是p，则判定p元素重复。

总结：

从下标0开始一直到n-1:

1. 先判断这个位置上是不是应该放这个数
   • 不是，则将这个数放回它应在的位置
     • 如果这个数应在的位置已经有了和这个数相等的数，说明这个数字是重复的
     • 如果这个数应在的数是其他数，则将这两个数交换位置，重新回到1.
   • 是，则继续向下遍历。

代码中尽管有两个循环，但是每个数字最多只要交换两次就能找到属于自己的位置，因此总的时间复杂度是O(n)，空间复杂度是O(1)

代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
      //遍历数组
        for(int i=0; i<nums.length;i++){
          //如果当前值不等于其下标
            while(nums[i] != i){
              	//如果当前值 不在它应该在的位置上。则将它放到它应该在位置上，不断重复
                if(nums[i] != nums[nums[i]]){
                    swap(nums,i,nums[i]);
                }else{
                  	//如果当前值 当前值应该在的位置已经有了对应的值 说明当前值是一个重复的值
                    return nums[i];
                }
            }   
        }
        return -1;
    }


    public static void swap(int[] nums ,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp ;
    }
}

参考书籍：剑指offer