在一個長度為 n 的數(shù)組里的所有數(shù)字都在 0 到 n - 1 的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的笔呀，但不知道有幾個數(shù)字是重復(fù)的灵巧。也不知道每個數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字官觅。例如，如果輸入長度為 7 的數(shù)組 {2,3,1,0,2,5,3}阐污，那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字 2休涤。
解法1：
數(shù)組排序，比較相鄰元素是否相等疤剑。時間復(fù)雜度為 O(nlogn)滑绒，空間復(fù)雜度為 O(1)闷堡。
解法2：
利用 HashSet 解決隘膘，時間復(fù)雜度為 O(n)，空間復(fù)雜度也為 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：
特殊解法弯菊，遍歷數(shù)組，假設(shè)第 i 個位置的數(shù)字為 j踱阿，則通過交換將 j 換到下標(biāo)為 j 的位置上管钳，直到所有數(shù)字都出現(xiàn)在自己對應(yīng)的下表處，或發(fā)生了沖突软舌。代碼中盡管有一個兩重循環(huán)才漆，但每個數(shù)字最多只要交換兩次就能找到屬于它自己的位置，因此總的時間復(fù)雜度為 O(n)佛点。所有操作都是在數(shù)組上進(jìn)行的醇滥，不需要額外分配內(nèi)存，因此空間復(fù)雜度為 O(1)超营。
// 可輸出所有重復(fù)的元素
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);
}
}
