寻找重复数[抽象二分/快慢指针/二进制枚举]

前言

保持有序对二分/抽象二分的敏感性；保持环问题/死循环对快慢指针的敏感性。

一、寻找重复数

二、抽象二分/快慢指针/二进制枚举

package everyday.doublePoint;

// 寻找重复数
public class FindDuplicate {
    
    /* 将自己放到自己的位置上，如果已经被占了，说明重复。 这个修改了数组，双指针，O(n),O(1) */
    public int findDuplicate(int[] nums) {
    
        for (int i = 0; i < nums.length; ) {
    
            if (nums[i] - 1 != i) {
    
                if (nums[nums[i] - 1] == nums[i]) return nums[i];
                // 交换位置
                int t = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            } else ++i;
        }
        return 1;
    }

    /* 题目要求，是不能修改数组的。所以要么双循环O(N^2^)/O(1)，要么hash记录O(N)/O(N). 而二分法可以完成不修改数组，O(NlogN)/O(1) 保持有序对二分法的敏感性，看到1-n联想到二分法，抽象二分。(其实二分和快慢指针都属于双指针类型) 数组中的元素是1-n，加上重复元素，一共就是n+1个元素，重复元素为1-n中的其中一个元素。 将区间[1,n]划分为[1,mid]/[mid,n],记录数组中小于等于mid的元素个数cnt，如果出现 cnt > mid的情况，说明重复元素小于等于mid。 */
    public int findDuplicate2(int[] nums) {
    
        int low = 1, high = nums.length - 1;
        while (low < high) {
    
            int mid = low + (high - low >>> 1);
            // 求小于等于mid的元素个数。
            int cnt = 0;
            for (int num : nums) cnt += num > mid ? 0 : 1;
            // 抽象判定规则，若小于等于mid的元素超过了mid个，则重复元素x <= mid
            if (cnt > mid) high = mid;
            else low = mid + 1;
        }
        return low;
    }

    /* 元素属于1-n,共n + 1个元素，若每次都取nums[nums[i]]表示：nums[i]走到下一跳nums[nums[i]]。 在index：1-n的闭环内跳，当碰到后面相同的元素时，又会跳到同一个地方继续前进，再次来到第2个重复的地方，又跳到前面同一个地方。 保持环/死循环对快慢指针的敏感性。 但是这里不仅仅单纯判定环，下一个关键问题是如何用快慢指针确定环的入口？ 解答见代码中的注释。 */
    public int findDuplicate3(int[] nums) {
    
        int fast = nums[nums[0]], slow = nums[0];
        while (fast != slow) {
    
            fast = nums[nums[fast]];// 在闭环内走两步。
            slow = nums[slow];// 在闭环内走一步。
        }
        // 在快指针是慢指针2倍的背景下，设起点到环口的长度是a,慢指针在环内走了b和快指针相遇。
        // 相遇时，慢指针走了a+b步，快指针走了2(a+b)步，可以理解为快指针走了a+b步，到达相遇地点，而剩下的a+b步则绕环走了k圈。
        // 设环长L,则a+b = kL -> a = kL - b = (k - 1)L + (L - b).
        // 设从相遇地点走c步到入口，则a=(k-1)L+c,所以从起点走a步到入口，快指针刚好走了k-1圈(回到相遇地点) & c步到达入口
        // 注：可证明：K>=1，即快指针至少走了一圈赶上了慢指针。
        slow = 0;
        while (slow != fast) {
    
            slow = nums[slow];
            fast = nums[fast];
        }
        return fast;
    }

    /* 二进制枚举法。 思考角度，按位展开，如果能找重复元素每一位是0还是1，就能得到重复元素。 设第i位，nums所有数展开为1的数是x，把1-n所有数展开为1的数是y，如果x > y，则表示重复元素第i位为1. */
    public int findDuplicate4(int[] nums) {
    
        int n = nums.length, ans = 0;
        int bit_max = 31;
        while (((n - 1) >> bit_max) == 0) {
    
            bit_max -= 1;
        }
        for (int bit = 0; bit <= bit_max; ++bit) {
    
            int x = 0, y = 0;
            for (int i = 0; i < n; ++i) {
    
                if ((nums[i] & (1 << bit)) != 0) {
    
                    x += 1;
                }
                if (i >= 1 && ((i & (1 << bit)) != 0)) {
    
                    y += 1;
                }
            }
            if (x > y) {
    
                ans |= 1 << bit;
            }
        }
        return ans;

        /* 作者：LeetCode-Solution 链接：https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 */
    }
}

总结

1）保持有序对二分/抽象二分的敏感性；
2）保持环问题/死循环对快慢指针的敏感性。

参考文献

[1] LeetCode 寻找重复数
[2] LeetCode 官方题解