算法1

image.png

image.png

//最优解法

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;
}