最近在刷题，准备记录一些值得参考的题目，也希望通过这种方式可以让自己印象更加深刻，本篇文章将讨论 数组中重复的数字 相关的一些题目。

题目

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

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

思路一 —— 排序

1. 将输入的数组排序（升序）
2. 从头到尾扫描排序后的数组找出重复的数字即可

该方法实现简单，但是对于一个长度为 n 的数组，排序该数组的时间复杂度为 O(nlogn)。

思路二 —— 哈希表

1. 从头到尾扫描数组每个数字
2. 判断哈希表里面是否已经包含该数字
3. 如果没有该数字，则把该数字放入哈希表
4. 如果哈希表中已经存在该数字，则找到一个重复的数字

该算法的时间复杂度为 O(n)，但是提高时间效率是以一个大小为 O(n) 的哈希表为代价的。

思路三 —— 推荐

我们注意到数组中的数字都在 0~n-1 的范围内。如果输入的数组中没有重复的数字，那么当数组排序后数字 i 将出现在下标为 i 的位置。

1. 从头到尾扫描数组中每个数字
2. 当扫描到下标为 i 的数字 m 时，首先比较这个数字 m 是不是等于 i。
   1. 如果是，则接着扫描下一个数字（说明数字本身在应该在的位置上）
   2. 如果不是，则那数字 m 和在第 m 个位置上的数字进行比较
      1. 如果和第 m 个数字相等，则找到了重复的数字（第i个和第m个是重复的数字）
      2. 如果和第 m 个数字不相等，就把第 i 个数字和第 m 个数字交换，把数字 m 放到属于它的位置上，然后继续重复比较，交换的过程，直到发现一个重复的数字，或者扫描结束（没有重复的数字）

我们以题目中的例子来进行说明

{5,0,3,6,5,2,3}

• 从该数组的第一个数字（位置0）开始扫描
• 第 0 个数字是 5, 0 和 5 不相等，则比较数字 5 和第 5 个位置上的数（数字2）
• 数字 5 和第 5 个位置上的数字 2 也不相等，则交换第 0 个位置和第 5 个位置上的数字，得到

{2,0,3,6,5,5,3}

• 交换后第 0 个位置的数字是 2，仍然不等于 0 ，继续比较、交换的过程
• 2 和第 2 个位置的数字 3 不相等，继续交换，交换后得到

{3,0,2,6,5,5,3}

• 交换后的 3 仍然不等于 0，继续比较、交换步骤
• 3 和第 3 个位置的数字 6 不相等，继续交换，交换后得到

{6,0,2,3,5,5,3}

• 交换后的 6 仍然不等于 0，继续比较、交换步骤
• 6 和第 6 个位置的数字 3 不相等，继续交换，交换后得到

{3,0,2,3,5,5,6}

• 交换后的 3 仍然不等于 0，继续比较、交换步骤
• 到这里 第 0 个位置的数字 3 和第 3 个位置的数字 3 出现了重复，即找到了重复的数字

该算法中每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是 O(n) ，由于是直接在输入数组上进行的操作，没有分配额外的内存空间，因此空间复杂度为 O(1) 。

下面是该算法的 JAVA 代码测试用例和实现：

测试用例

public class DuplicateNumberArrayTest {

    @Test
    public void testNormalArray() {
        assertEquals(3, new DuplicateNumberArray().findDuplicationNumber(new int[]{5, 0, 3, 6, 1, 2, 3}));
        assertEquals(2, new DuplicateNumberArray().findDuplicationNumber(new int[]{5, 0, 2, 6, 1, 2, 3}));
        assertEquals(5, new DuplicateNumberArray().findDuplicationNumber(new int[]{5, 0, 2, 6, 5, 1, 3}));
        assertEquals(4, new DuplicateNumberArray().findDuplicationNumber(new int[]{4, 0, 2, 6, 5, 4, 3}));
    }

    @Test
    public void testMultipleDuplicationNumber() {
        assertEquals(5, new DuplicateNumberArray().findDuplicationNumber(new int[]{5, 0, 3, 5, 1, 1, 3}));
        assertEquals(1, new DuplicateNumberArray().findDuplicationNumber(new int[]{1, 0, 3, 5, 1, 1, 3}));
    }

    @Test
    public void testNoDuplicationNumber() {
        assertEquals(-1, new DuplicateNumberArray().findDuplicationNumber(new int[]{5, 0, 3, 2, 1, 6, 4}));
    }

    @Test
    public void testInvalidArray() {
        assertEquals(-1, new DuplicateNumberArray().findDuplicationNumber(new int[]{5, 0, -1, 2, 1, 6, 4}));
    }

    @Test
    public void testNullArray() {
        assertEquals(-1, new DuplicateNumberArray().findDuplicationNumber(null));
    }
}

实现

/**
 * 在一个长度为 n 的数组里，所有的数字都在 0~n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了多少次。请找出数组中任意一个重复的数字。
 *
 * @author Aaric
 */
public class DuplicateNumberArray {

    /**
     * 找出数组中任意一个重复的数字
     *
     * @param array 输入的数组
     * @return 数组中重复的数字或者 -1 （如果输入无效、或者没有重复的数字）
     */
    public int findDuplicationNumber(int[] array) {
        if (array == null) {
            return -1;
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] >= array.length) {
                return -1;
            }
            while (array[i] != i) {
                if (array[i] == array[array[i]]) {
                    return array[i];
                } else {
                    int temp = array[i];
                    array[i] = array[array[i]];
                    array[temp] = temp;
                }
            }
        }
        return -1;
    }
}

记住先写测试用例再写代码！