SwordPointToOffer(51): 数组中重复的数字

发表于   |   分类于

题目

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

例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

分析

方法一

排序，时间复杂度$O(n\log{n})$。

方法二

借助哈希表记录数字的次数，时间复杂度$O(n)$，空间复杂度$O(n)$。

方法三

我们注意到数组中的数字都在 0 到 n-1 中。如果这个数组中没有重复的数字，那么当数组排序之后数字 i 将出现在下标为 i 的位置。由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。

现在让我们重排这个数组，依然从头到尾一次扫描这个数组中的每个数字。当扫描到下标为 i 的数字时，首先比较这个数字（用 m 表示）是不是等于 i。如果是，接着扫描下一个数字。如果不是，再拿它和第 m 个数字进行比较。 如果它和第m个数字相等，就找到了一个重复的数字（该数字在下标为 i 和 m 的位置都出现了）。如果它和第 m 个数字不相等，就把第 i 个数字和第 m 个数字交换，把 m 放到属于它的位置。接下来再重读这个比较、交换的过程，直到我们发现一个重复的数字。

以数组{2,3,1,0,2,5,3}为例来分析找到重复数字的步骤。数组的第 0 个数字（从 0 开始计数，和数组的下标保持一致）是 2，与它的下标不相等，于是把它和下标为 2 的数字 1 交换。交换之后的数组是{1.3.2.0.2.5.3}。此时第 0 个数字是 1，仍然与它的下标不相等，继续把它和下标为 1 的数字 3 交换，得到数组{3,1,2,0,2,5,3}.接下来继续交换第 0 个数字 3 和第 3 个数字 0，得到数组{0,1,2,3,2,5,3}。此时第 0 个数字的数值为 0，接着扫描下一个数字。在接下来的几个数字中，下标为 1，2，3 的三个数字分别为 1，2，3 它们的下标和数值都分别相等，因此不需要做任何操作。接下来扫描到下标为 4 的数字 2。由于它的数值与它的下标不相等，再比较它和下标为 2 的数字。注意到此时数组中下标为 2 的数字也是 2，也就是数字在下标为 2 和下标为 4 的两个位置都出现了，因此找到一个重复的数字。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class DuplicateInArray {
    public static void main(String[] args) {
        DuplicateInArray test = new DuplicateInArray();
        System.out.println(test.handle(new int[]{3,5,1,1,0,4}));
    }
    
    public int handle(int[] num){
        if (num == null || num.length <= 0)
            return -1;
        
        // 检测输入是否在[0, num.length-1]之间
        for (int i : num){
            if (i < 0 || i >= num.length)
                return -1;
        }
        
        for (int i = 0; i < num.length; ++i){
            while (num[i] != i){
                if (num[i] == num[num[i]]){
                    return num[i];
                }else {
                    swap(num, i, num[i]);
                }
            }
        }
        return -1;
    }
    
    private void swap(int[] num, int i, int j){
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
}