在一个长度为 n 的数组里的所有数字都在 0 到 n - 1 的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字 2。
解法1：
数组排序，比较相邻元素是否相等。时间复杂度为 O(nlogn)，空间复杂度为 O(1)。
解法2：
利用 HashSet 解决，时间复杂度为 O(n)，空间复杂度也为 O(n)。
public static boolean duplicateHashSet(int[] array) {
if (array == null || 0 == array.length)
return false;
for (int i = 0; i < array.length; i++) {
if (array[i] < 0 || array[i] > array.length - 1)
return false;
}
Set<Integer> hashSet = new HashSet<>();
for (int i = 0; i < array.length; i++) {
if (!hashSet.add(array[i])) {
System.out.println(array[i]);
return true;
}
}
return false;
}
解法3：
特殊解法，遍历数组，假设第 i 个位置的数字为 j，则通过交换将 j 换到下标为 j 的位置上，直到所有数字都出现在自己对应的下表处，或发生了冲突。代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度为 O(n)。所有操作都是在数组上进行的，不需要额外分配内存，因此空间复杂度为 O(1)。
// 可输出所有重复的元素
public static Collection duplicate(int[] array, Collection<Integer> c) {
if (array == null || 0 == array.length)
return null;
for (int i = 0; i < array.length; i++) {
if (array[i] < 0 || array[i] > array.length - 1)
return null;
}
for (int i = 0; i < array.length; i++) {
while (array[i] != i) {
if (array[i] == array[array[i]]) {
System.out.println(array[i]);
c.add(array[i]);
break;
}
int tmp = array[i];
array[i] = array[tmp];
array[tmp] = tmp;
}
}
完整代码
import java.util.*;
public class RepeatNum {
public static int[] array;
public static Collection<Integer> collection;
public static boolean duplicateHashSet(int[] array) {
if (array == null || 0 == array.length)
return false;
for (int i = 0; i < array.length; i++) {
if (array[i] < 0 || array[i] > array.length - 1)
return false;
}
Set<Integer> hashSet = new HashSet<>();
for (int i = 0; i < array.length; i++) {
if (!hashSet.add(array[i])) {
System.out.println(array[i]);
return true;
}
}
return false;
}
public static Collection duplicate(int[] array, Collection<Integer> c) {
if (array == null || 0 == array.length)
return null;
for (int i = 0; i < array.length; i++) {
if (array[i] < 0 || array[i] > array.length - 1)
return null;
}
for (int i = 0; i < array.length; i++) {
while (array[i] != i) {
if (array[i] == array[array[i]]) {
System.out.println(array[i]);
c.add(array[i]);
break;
}
int tmp = array[i];
array[i] = array[tmp];
array[tmp] = tmp;
}
}
return c;
}
public static void main(String[] args) {
array = new int[]{2, 3, 1, 0, 2, 5, 3};
collection = new ArrayList<>();
collection = duplicate(array, collection);
boolean bb = duplicateHashSet(array);
System.out.println(collection.toString());
System.out.println(bb);
}
}
