## JZ50. 数组中重复的数字

### 答案：

1，使用集合set

```import java.util.HashSet;
import java.util.Set;
public class Solution {
// Parameters:
//    numbers:     an array of integers
//    length:      the length of array numbers
//    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
//                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
//    这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value:       true if the input is valid, and there are some duplications in the array number
//                     otherwise false
public boolean duplicate(int numbers[], int length, int[] duplication) {
if (numbers == null || numbers.length == 0)
return false;
Set<Integer> set = new HashSet<>();
for (int num : numbers) {
duplication[0] = num;
return true;
}
}
return false;
}
}```

2，先排序在查找

```public boolean duplicate(int numbers[], int length, int[] duplication) {
if (numbers == null || numbers.length == 0)
return false;
//先排序
Arrays.sort(numbers);
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] == numbers[i - 1]) {
duplication[0] = numbers[i];
return true;
}
}
return false;
}```

3，使用临时数组

```public boolean duplicate(int numbers[], int length, int[] duplication) {
if (numbers == null || numbers.length == 0)
return false;
int[] temp = new int[length];
for (int i = 0; i < length; i++) {
temp[numbers[i]]++;
if (temp[numbers[i]] > 1) {
duplication[0] = numbers[i];
return true;
}
}
return false;
}```

4，放到指定的位置

```public boolean duplicate(int numbers[], int length, int[] duplication) {
if (numbers == null || numbers.length == 0)
return false;
for (int i = 0; i < length; i++) {
//位置正确，先不用管
if (i == numbers[i])
continue;
//出现了重复，直接返回
if (numbers[i] == numbers[numbers[i]]) {
duplication[0] = numbers[i];
return true;
}
//交换
int temp = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = temp;
//这里的i--是为了抵消掉上面的i++，
//交换之后需要原地再比较
i--;
}
return false;
}```