//最优解法
bool duplicate(int numbers[], int lenght, int *duplication) {
//非空判断
if (numbers == nil || lenght <= 0) {
return false;
}
//数组元素有效性判断
for (int i = 0; i < lenght; i++) {
if (numbers[i] < 0 || numbers[i] > lenght - 1) {
return false;
}
}
for (int i = 0; i < lenght; i ++) {
while (numbers[i] != i) {
if (numbers[i] == numbers[numbers[i]]) {
*duplication = numbers[I];
return true;
}
int temp = numbers[I];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
时间复杂度o(n),空间复杂度o(1)不需要分配空间
//其它解法 排序
//hash
bool duplicateHash(int numbers[], int lenght, int *duplication) {
//非空判断
if (numbers == nil || lenght <= 0) {
return false;
}
//数组元素有效性判断
for (int i = 0; i < lenght; i++) {
if (numbers[i] < 0 || numbers[i] > lenght - 1) {
return false;
}
}
int *result = (int *)malloc(sizeof(int) * lenght);
for (int i = 0; i < lenght; i ++) {
result[i] = 0;
}
for (int i = 0; i < lenght; i ++) {
int index = numbers[i];
if (result[index] == 0) {
result[index] ++;
} else {
*duplication = numbers[i];
return true;
}
}
return false;
}