题目描述(中等难度)

1n 范围内的某些数,放到大小为 n + 1 的数组中,数组要放满,所以一定会有一个重复的数字,找出这个重复的数字。比如 [2,2,2,1]

假设重复的数字只有一个。

解法一和解法二先不考虑题目中 Note 的要求。

解法一 排序

最简单的,先排序,然后两两判断即可。

public int findDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return nums[i];
        }
    }
    return -1;
}

解法二 HashSet

判断重复数字,可以用 HashSet,这个方法经常用了。

public int findDuplicate(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        if (set.contains(nums[i])) {
            return nums[i];
        }
        set.add(nums[i]);
    }
    return -1;
}

解法三 二分查找

参考 这里%3A-O(nlog(n)) 。

我们知道二分查找要求有序,但是给定的数组不是有序的,那么怎么用二分查找呢?

原数组不是有序,但是我们知道重复的那个数字肯定是 1n 中的某一个,而 1,2...,n 就是一个有序序列。因此我们可以对 1,2...,n 进行二分查找。

mid = (1 + n) / 2,接下来判断最终答案是在 [1, mid] 中还是在 [mid + 1, n] 中。

我们只需要统计原数组中小于等于 mid 的个数,记为 count

如果 count > mid ,鸽巢原理,在 [1,mid] 范围内的数字个数超过了 mid ,所以一定有一个重复数字。

否则的话,既然不在 [1,mid] ,那么最终答案一定在 [mid + 1, n] 中。

public int findDuplicate(int[] nums) {
    int n = nums.length - 1;
    int low = 1;
    int high = n;
    while (low < high) {
        int mid = (low + high) >>> 1;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) {
                count++;
            }
        }
        if (count > mid) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

解法四 二进制

参考 这里-solution-using-bit-manipulation-in-10-lines)。137 题 以及 169 题 其实已经用过这个思想,但还是不容易往这方面想。

主要就是我们要把数字放眼到二进制。

然后依次统计数组中每一位 1 的个数,记为 a[i]。再依次统计 1n 中每一位 1 的个数,记为 b[i]i 代表的是哪一位,因为是 int,所以范围是 032

记重复的数字是 res

如果 a[i] > b[i] 也就意味着 res 当前位是 1

否则的话,res 当前位就是 0

举个例子吧,1 3 4 2 2

1 3 4 2 2 写成 2 进制
1 [0 0 1]
3 [0 1 1]
4 [1 0 0]
2 [0 1 0]
2 [0 1 0]

把 1 到 n,也就是 1 2 3 4 也写成 2 进制
1 [0 0 1]
2 [0 1 0]
3 [0 1 1]
4 [1 0 0]

依次统计每一列 1 的个数, res = XXX

原数组最后一列 1 的个数是 2
14 最后一列 1 的个数是 2
2 不大于 2,所以当前位是 0, res = XX0

原数组倒数第二列 1 的个数是 3
14 倒数第二列 1 的个数是 2
3 大于 2,所以当前位是 1, res = X10

原数组倒数第三列 1 的个数是 1
14 倒数第三列 1 的个数是 1
1 不大于 1,所以当前位是 0, res = 010

所以 res = 010, 也就是 2

上边是重复数字的重复次数是 2 的情况,如果重复次数大于 2 的话上边的结论依旧成立。

简单的想一下,1 3 4 2 2 ,因为 2 的倒数第二位的二进制位是 1,所以原数组在倒数第二列中 1 的个数会比14 这个序列倒数第二列中 1 的个数多 1 个。如果原数组其他的数变成了 2 呢?也就2 的重复次数大于 2

如果是 1 变成了 2,数组变成 2 3 4 2 2 , 那么倒数第二列中 1 的个数又会增加 1

如果是 3 变成了 2,数组变成 1 2 4 2 2 , 那么倒数第二列中 1 的个数不会变化。

所以不管怎么样,如果重复数字的某一列是 1,那么当前列 1 的个数一定会比 1n 序列中 1 的个数多。

public int findDuplicate(int[] nums) {
    int res = 0;
    int n = nums.length; 
    //统计每一列 1 的个数
    for (int i = 0; i < 32; i++) {
        int a = 0;
        int b = 0;
        int mask = (1 << i);
        for (int j = 0; j < n; j++) {
            //统计原数组当前列 1 的个数
            if ((nums[j] & mask) > 0) {
                a++;
            }
            //统计 1 到 n 序列中当前列 1 的个数
            if ((j & mask) > 0) {
                b++;
            }
        }
        if (a > b) {
            res = res | mask;
        }
    }
    return res;
}

解法五

参考 这里-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.) ,一个神奇的解法了。

把数组的值看成 next 指针,数组的下标看成节点的索引。因为数组中至少有两个值一样,也说明有两个节点指向同一个位置,所以一定会出现环。

举个例子,3 1 3 4 2 可以看成下图的样子。

nums[0] = 3
nums[3] = 4
nums[4] = 2
nums[2] = 3

所以我们要做的就是找到上图中有环链表的入口点 3,也就是 142 题

具体证明不说了,只介绍方法,感兴趣的话可以到 142 题 看一下。

我们需要快慢指针,同时从起点出发,慢指针一次走一步,快指针一次走两步,然后记录快慢指针相遇的点。

之后再用两个指针,一个指针从起点出发,一个指针从相遇点出发,当他们再次相遇的时候就是入口点了。

public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    //寻找相遇点
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    //slow 从起点出发, fast 从相遇点出发, 一次走一步
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

看起来比较简单的一道题,思想用了不少。经典的二分,从二进制思考问题,以及最后将问题转换的思想,都很经典。

results matching ""

    No results matching ""