package com.lee.algorithm.eor;

/***
 * 异或运算：位相同则为0，位不同则为1；也可称做无进位相加
 * 异或运算规则：
 *   0 ^ N = N
 *   N ^ N = 0
 *   N ^ M = M ^ N
 *   (N ^ M) ^ Y = N ^ (M ^ Y)
 * @description: 异或 巧用
 * @author : 青石路
 * @date: 2021/11/18 14:12
 */
public class ExclusiveORTest {

    public static void main(String[] args) {
        int[] objArr = new int[]{1,2,3,4,5,6,1,2,3,4,5,6,6,6,1,2};
        int[] oddTimesNum2 = findOddTimesNum2(objArr);
        System.out.println("oddTimes num : " + oddTimesNum2[0] + ", " + oddTimesNum2[1]);
    }

    /**
     * 
     * 不用额外的变量交换两个变量的值
     *   i != j， 否则会出问题（两个变量指向的是不同的两块内存区域）
     * @author 博客园 @ 青石路
     * @param arr
     * @param i
     * @param j
     */
    public static void swapWithoutOtherVar(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    /**
     * 已知一串数中，只有 1 个数字出现了奇数次，
     *  其他数字都出现了偶数次，如何快速找到这个奇数次的数字
     * 要求：时间复杂度：O(N)， 空间复杂度 O(1)
     * @author 博客园 @ 青石路
     * @param arr
     */
    public static int findOddTimesNum(int[] arr) {
        int eor = 0;
        for (int cur : arr) {
            eor ^= cur;
        }
        return eor;
    }

    /**
     * 已知一串数中，有 2 个数字出现了奇数次，其他数字都出现了偶数次，如何快速找到 2 个奇数次的数字
     * 要求：时间复杂度：O(N)， 空间复杂度 O(1)
     * 分析：
     *      假设出现了奇数次的数字是：a、b，a != b
     *      所有数字都进行异或运算后，得到的结果是：int eor = a ^ b
     *      a != b，所以 eor != 0，那么 eor 肯定有某一个二进制位是 1
     * @author 博客园 @ 青石路
     * @param arr
     */
    public static int[] findOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int cur : arr) {
            eor ^= cur;
        }
        // 此时 eor = a ^ b; a != b，所以 eor != 0，那么 eor 肯定有某一个二进制位是 1
        // 取 eor 二进制最右（左）边的 1
        int rightOne = eor & (~eor + 1);  // rightOne 所有二进制位中只有一个 1 ，其他都是 0

        int onlyOne = 0;
        // int otherOne = 0;
        for(int cur : arr) {
            /**
             * 通过 rightOne 将全部数据拆成两部分：cur & rightOne = 0 和 cur & rightOne != 0
             * a、b 分别落在两侧，其他数字只会落在某一侧（并且是偶数个）
             * 全部数据就被拆分成两个 findOddTimesNum 的数据模型了
             */
            if ((cur & rightOne) == 0) {
                onlyOne ^= cur;
            } /*else {
                otherOne ^= cur;
            }*/
        }
        // System.out.println("onlyOne = " + onlyOne + ", otherOne = " + otherOne);

        // onlyOne = a、b 中的某一个
        // 另一个 = onlyOne ^ eor = onlyOne ^ (a ^ b)
        return new int[]{onlyOne, onlyOne ^ eor};
    }

    /**
     * 一串数字包含 n-1 个成员，这些成员是 1 到 n 之间的整数，
     * 且没有重复，请找出缺少的那个数字
     * 要求：时间复杂度：O(N)， 空间复杂度 O(1)
     * @author 博客园 @ 青石路
     * @param arr
     * @return
     */
    public static int findMissNum(int[] arr) {
        int sum = 0;
        // 先求和，1 + 2 + ... + n
        for (int i=1; i<=arr.length+1; i++) {
            sum += i;
        }

        // 再逐个减去这串数字
        for(int i=0; i<arr.length; i++) {
            sum -= arr[i];
        }

        return sum;
    }

    /**
     * 一串数字包含 n-1 个成员，这些成员是 1 到 n 之间的整数，
     * 且没有重复，请找出缺少的那个数字
     * 要求：时间复杂度：O(N)， 空间复杂度 O(1)
     * @author 博客园 @ 青石路
     * @param arr
     * @return
     */
    public static int findMissNumPlus(int[] arr) {
        int eor = 0;
        for(int i=0; i<arr.length; i++) {
            eor ^= arr[i] ^ (i+1);
        }
        eor ^= arr.length + 1;
        return eor;
    }

    /**
     * 一串数字包含 n+1 个成员，这些数字是 1 到 n 之间的整数，只有一个数字出现了两次，
     * 其他数字都只出现一次，请找出重复出现的那个数字
     * 要求：时间复杂度：O(N)， 空间复杂度 O(1)
     * @author 博客园 @ 青石路
     * @param arr
     * @return
     */
    public static int findRepeatNum(int[] arr) {
        int eor = 0;
        int n = arr.length-1;
        for(int i=0; i<n; i++) {
            eor ^= arr[i] ^ (i+1);
        }
        eor ^= arr[n];
        return eor;
    }
}