[50] 数组中的重复数字(简单)
[50] 数组中的重复数字(简单)

题目描述

在一个长度为 n 的数组里的所有数字都在 0n-1 的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。
请找出数组中任一一个重复的数字。 例如,如果输入长度为 7 的数组 [2,3,1,0,2,5,3],那么对应的输出是 2 或者 3
存在不合法的输入的话输出 -1
输入:[2,3,1,0,2,5,3]
返回值:2
说明:23都是对的

解题思路

双循环遍历

两重遍历,第一重将当前数字存起来,与第二重遍历的所有数字依次比对。
/**
 * 两重遍历,依次比对
 * T(n^2) S(1)
 */
public int duplicate(int[] numbers) {
    for (int i = 0; i < numbers.length; i++) {
        int buf = numbers[i];
        for (int j = i + 1; j < numbers.length; j++) {
            if (buf == numbers[j]) {
                return buf;
            }
        }
    }
    return -1;
}

哈希表

建立一个哈希表,然后依次遍历数组,每次先判断数字是否在哈希表中,如果在就直接返回,否则就添加到哈希表中。
/**
 * 哈希表
 * T(n) S(n)
 */
public int duplicate(int[] numbers) {
    List<Integer> table = new ArrayList<>();
    for (int i = 0; i < numbers.length; i++) {
        if (table.contains(numbers[i])) {
            return numbers[i];
        }
        table.add(numbers[i]);
    }
    return -1;
}

原地交换

利用题目中:数组里的所有数字都在 0n-1 的范围内。遍历时对当前数字进行判断,如果其下标不等于其本身,就先和为其本身的那个元素交换,使得 numbers[i] == numbers[numbers[i]]直到下标和元素值一样才继续往下遍历,如此一来,发现已经有下标等于其本身的元素的话,就说明存在重复元素。
/**
 * 原地交换
 * T(n) S(1)
 */
public int duplicate(int[] numbers) {
    int i = 0;
    while (i < numbers.length) {
        int temp = numbers[i];
        // 直到交换到下标和元素一样才继续走
        if (temp == i) {
            i++;
            continue;
        }
        // numbers[i] == numbers[numbers[i]] 表示存在以当前元素作为下标的元素(找到重复数字)
        if (numbers[temp] == temp) {
            return temp;
        }
        // numbers[i] 和 numbers[numbers[i]] 交换,使得 numbers[numbers[i]] 的下标 == 元素
        numbers[i] = numbers[temp];
        numbers[temp] = temp;
    }
    return -1;
}