数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2

分析

最简单的做法是排序后对比，时间空间复杂度分别是O(nlogn)和O(1)。也可利用HashSet特性解决。但都不是最优解。

题干说到，数字是从 0 到 n-1。那么可以将遇到的数据进行归位（下标=值)。

扫描数组，下标 i 的数字，首先比较该值 m 是否等于 i.

• 如果是，则接着扫描下一个数字；
• 如果不是，则拿值 m 与第 m 个数比较。
  • 如果 m 与第 m 个数相等，则说明重复。
  • 如果不等将 m 与第 m 个数交换，将 m "归位"，重复比较交换，直到发现重复。

比如存在数组 nums:2,1,0,2

• 下标 i = 0时，nums[0] = 2 != i 。 判断 nums[i] 不等于 nums[nums[i]], 不等于则交换nums[i] 和nums[nums[i]]。之后数组为：0,1,2,2
• 此时下标不变， i = 0，nums[0] = 0 = i 。 进行下一组。
• i = 1，nums[1] = 1 = i 。 进行下一组。
• i = 2，nums[2] = 2 = i 。 进行下一组。
• i = 3，nums[3] = 2 != i 。 但 nums[3] 等于 nums[nums[3]]，说明重复。

实现

public boolean duplicate(int nums[],int length,int [] duplication) {
        if(nums == null || length == 0){
            return false;
        }
        for(int i = 0;i < length;i++){
            while(nums[i] != i){
                if(nums[i] == nums[nums[i]]){
                    duplication[0] = nums[i];
                    return true;
                }
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
        }
        return false;
    }