数组中重复的数字 -- java

数组中重复的数字 -- java 题目一 题目描述

找出数组中重复的数字。

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

解题思路

差（时间复杂度为O(nlogn)，空间复杂度为O(1)）
先对数组排序，然后从头扫描排序后的数组就可以了。

中（时间复杂度为O(n)，空间复杂度为O(n)）
从头到尾按顺序扫描数组的每个数字，每扫描到一个数字的时候就判断该哈希表是否已经存在该数字，如果哈希表还没有这个数字，就把它加入到哈希表中，如果哈希表已经有这个数字，就找到了一个重复的数字。

好（时间复杂度为O(n)，空间复杂度为O(1)）
关键：这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素放到第 i 个位置上。

从头到尾依次扫描这个数字中的每个数字，当扫描到下标为i的数字，首先比较这个数字（用m表示）是不是等于i，如果是，则继续扫描下一个，如果不是，就就拿它和第m个数字比较，如果它和第m个数字相等，就找到了一个重复的数字；如果不相等，就把第i个数字与第m个数字交换，把m放到属于它的位置，接下来再重复这个比较，交换的过程，直到我们发现一个重复的数字。

具体过程：（以输入{2, 3, 1, 0, 2, 5}为例）

position-0 : (2,3,1,0,2,5) // 2 <-> 1
             (1,3,2,0,2,5) // 1 <-> 3
             (3,1,2,0,2,5) // 3 <-> 0
             (0,1,2,3,2,5) // already in position
position-1 : (0,1,2,3,2,5) // already in position
position-2 : (0,1,2,3,2,5) // already in position
position-3 : (0,1,2,3,2,5) // already in position
position-4 : (0,1,2,3,2,5) // nums[i] == nums[nums[i]], exit

正确解题

public class Duplicate1 {
    
    public static boolean duplicate(int numbers[], int[] duplication) {
        // 杜绝数组为空
        if (numbers == null || numbers.length == 0) {
            return  false;
        }
        // 杜绝非法数字
        for(int i = 0; i < numbers.length; i++) {
            if (numbers[i] < 0 || numbers[i] > numbers.length-1) {
                return false;
            }
        }

        for (int i = 0; i < numbers.length; i++) {
            while (numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                // 交换numbers[i]和numbers[numbers[i]]
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }
}

题目二 题目描述

不修改数组找出重复的数字。

在一个长度为 n+1 的数组里的所有数字都在 1 到 n 的范围内。 所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字。但不能修改输入的数组。例如，如果输入长度为 7 的数组 {2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是第一个重复的数字 2 或 3 。

解题思路

思路一（时间复杂度为O(n),空间复杂度为O(n)）
创建一个长度为 n+1 的辅助数组，然后逐一把原数组赋值到辅助数组，如果被赋值的数字是m，则把它赋值到辅助数组中下标为m的位置。这样是很容易发现哪个数字是重复的。

或者从头到尾按顺序扫描数组的每个数字，每扫描到一个数字的时候就判断该哈希表是否已经存在该数字，如果哈希表还没有这个数字，就把它加入到哈希表中，如果哈希表已经有这个数字，就找到了一个重复的数字。

思路二（时间复杂度为O(nlogn),空间复杂度为O(1)）
我们把从 1 到 n 的数字从中间的数字 m 分为两步，前面一半为 1 到 m ，后面一半为 m+1 到 n 。如果 1 到 n 的数字的数目超过 m ，那么这一半里面一定包含重复的数字；否则另一半 m+1 到 n 的区间里一定包含重复的数字。我们可以继续把包含重复数字的区间一分为二，直到找到一个重复数字。这个过程和 二分查找算法 很类似，只是多了一步统计区间里数字的数目。

具体过程：（以输入{2, 3, 5, 4, 3, 2, 6, 7}为例）

step-1 : m=4 and count(<=4 && >=1) = 5 => duplicaiton in [1,2,3,4]
step-2 : m=2 and count(<=2 && >=1) = 2 => duplicaiton in [3,4]
step-3 : m=3 and count(<=3 && >=3) = 2 => duplicaiton in [3,3]
step-4 : end = start and count(<=3 && >=3) = 2 => duplicaiton = 3

PS：这种思路比思路一的时间复杂度高，相当于以时间换空间。

需要注意，这种算法不能保证找出所有重复的数字。例如，该算法不能找出数组{2,3,5,4,3,2,6,7}中重复的数字2。这是因为在1-2的范围里有1和2两个数字，这个范围里的数字也出现2次，此时我们用该算法不能确定是每个数字各出现一次还是某个数字出现了两次。

正确解题

public class Duplicate2 {
    public static int getDuplication(int[] numbers) {
        // 杜绝数组为空或长度为0
        if (numbers == null || numbers.length == 0) {
            return -1;
        }

        int start = 1;
        int end = numbers.length-1;
        while (end >= start) {
            int middle = ((end-start)>>1) + start;
            int count = countRange(numbers, start, middle);
            if (end == start) {
                // 发现某个数字出现1次以上
                if (count > 1) {
                    return start;
                } else {
                    break;
                }
            }
            if (count > (middle-start+1)) {
                // 在前一段有重复数字
                end = middle;
            } else {
                // 在后一段有重复数字
                start = middle+1;
            }
        }
        return -1;
    }

    public static int countRange(int[] numbers, int start, int end) {
        // 杜绝数组为空或长度为0
        if(numbers == null || numbers.length == 0) {
            return 0;
        }

        int count = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] >= start && numbers[i] <= end) {
                count++;
            }
        }
        return count;
    }
}

---

来源：

《剑指offer》
Coding-Interviews/数组中重复的数字.md at master · todorex/Coding-Interviews