Find duplicates [Abstract binary / fast and slow pointer / binary enumeration]

Preface

Keep order and dichotomy / Sensitivity of abstract dichotomy ; Retention ring problem / The sensitivity of the loop to the speed pointer .

One 、 Look for repetitions

Two 、 Abstract dichotomy / Speed pointer / Binary enumeration

package everyday.doublePoint;

//  Look for repetitions 
public class FindDuplicate {
    
    /*  Put yourself in your place , If it has been occupied , Repeated description .  This modifies the array , Double pointer ,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];
                //  Swap places 
                int t = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            } else ++i;
        }
        return 1;
    }

    /*  Subject requirements , You cannot modify the array . So either double circulation O(N^2^)/O(1), or hash Record O(N)/O(N).  Dichotomy can be done without modifying the array ,O(NlogN)/O(1)  Keep order and be sensitive to dichotomy , notice 1-n Associate with dichotomy , Abstract dichotomy .( In fact, both bisection and fast and slow pointers belong to the double pointer type )  The elements in the array are 1-n, Add repeating elements , All together n+1 Elements , The repeating element is 1-n One of the elements in .  The interval [1,n] Divided into [1,mid]/[mid,n], Record array is less than or equal to mid Number of elements of cnt, If appear  cnt > mid The situation of , It indicates that the repeating element is less than or equal to mid. */
    public int findDuplicate2(int[] nums) {
    
        int low = 1, high = nums.length - 1;
        while (low < high) {
    
            int mid = low + (high - low >>> 1);
            //  Find less than or equal to mid Number of elements of .
            int cnt = 0;
            for (int num : nums) cnt += num > mid ? 0 : 1;
            //  Abstract decision rules , If it is less than or equal to mid The element of exceeds mid individual , Then repeat the element x <= mid
            if (cnt > mid) high = mid;
            else low = mid + 1;
        }
        return low;
    }

    /*  The element belongs to 1-n, common n + 1 Elements , If you take it every time nums[nums[i]] Express ：nums[i] Go to the next jump nums[nums[i]].  stay index：1-n Closed loop jump , When you encounter the same element later , Will jump to the same place and continue to move forward , Come again to the 2 A repetition , Jump to the same place in front again .  Retaining ring / The sensitivity of the loop to the speed pointer .  But here is more than just a decision ring , The next key problem is how to use the fast and slow pointer to determine the entrance of the ring ？  See the comments in the code for the solution . */
    public int findDuplicate3(int[] nums) {
    
        int fast = nums[nums[0]], slow = nums[0];
        while (fast != slow) {
    
            fast = nums[nums[fast]];//  Take two steps in the closed loop .
            slow = nums[slow];//  Take a step in the closed loop .
        }
        //  The fast pointer is the slow pointer 2 Times in the background , Let the length from the starting point to the ring mouth be a, The slow pointer walked in the ring b Meet the fast pointer .
        //  When we met , Slow down a+b Step , It's almost gone 2(a+b) Step , It can be understood as that the pointer is gone a+b Step , Arrive at the meeting place , And the rest of the a+b Step then walked around k circle .
        //  Set ring length L, be a+b = kL -> a = kL - b = (k - 1)L + (L - b).
        //  Let's go from the meeting place c Step to the entrance , be a=(k-1)L+c, So go from the starting point a Step to the entrance , The pointer is just ready to go k-1 circle ( Return to the place of meeting ) & c Step to the entrance 
        //  notes ： It can be proved that ：K>=1, That is, the fast pointer walked at least one circle to catch up with the slow pointer .
        slow = 0;
        while (slow != fast) {
    
            slow = nums[slow];
            fast = nums[fast];
        }
        return fast;
    }

    /*  Binary enumeration .  Think about it , Expand by bit , If you can find repeated elements, each one is 0 still 1, You can get repeated elements .  Set the first i position ,nums All numbers expand to 1 The number of is x, hold 1-n All numbers expand to 1 The number of is y, If x > y, Then it means that the repeating element number i Position as 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;

        /*  author ：LeetCode-Solution  link ：https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/  source ： Power button （LeetCode）  The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source . */
    }
}

summary

1） Keep order and dichotomy / Sensitivity of abstract dichotomy ;
2） Retention ring problem / The sensitivity of the loop to the speed pointer .

reference

[1] LeetCode Look for repetitions
[2] LeetCode Official explanation