最近在刷题，准备记录一些值得参考的题目，也希望通过这种方式可以让自己印象更加深刻，本篇文章将讨论 数组中重复的数字 相关的一些题目。
题目
在一个长度为 n 的数组里，所有的数字都在 0~n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了多少次。请找出数组中任意一个重复的数字。
例如，如果输入长度为7的数组 {5,0,3,6,5,2,3}，那么对应的输出是重复的数字 3 或者 5。
思路一 —— 排序
- 将输入的数组排序（升序）
- 从头到尾扫描排序后的数组找出重复的数字即可
该方法实现简单，但是对于一个长度为 n 的数组，排序该数组的时间复杂度为 O(nlogn)。
思路二 —— 哈希表
- 从头到尾扫描数组每个数字
- 判断哈希表里面是否已经包含该数字
- 如果没有该数字，则把该数字放入哈希表
- 如果哈希表中已经存在该数字，则找到一个重复的数字
该算法的时间复杂度为 O(n)，但是提高时间效率是以一个大小为 O(n) 的哈希表为代价的。
思路三 —— 推荐
我们注意到数组中的数字都在 0~n-1 的范围内。如果输入的数组中没有重复的数字，那么当数组排序后数字 i 将出现在下标为 i 的位置。
- 从头到尾扫描数组中每个数字
- 当扫描到下标为 i 的数字 m 时，首先比较这个数字 m 是不是等于 i。
- 如果是，则接着扫描下一个数字（说明数字本身在应该在的位置上）
- 如果不是，则那数字 m 和在第 m 个位置上的数字进行比较
- 如果和第 m 个数字相等，则找到了重复的数字（第i个和第m个是重复的数字）
- 如果和第 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;
}
}
记住先写测试用例再写代码！
