02 异或运算

第2节.pptx

1 异或运算的应用

题目1：不用额外变量交换2个数

 /**
     * 如何不用额外变量交换两个数
     * @param a
     * @param b
     */
    public static void swap(int a, int b) {
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
    }

题目2：一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数

 /**
     * 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
     *
     * @param arr
     * @return
     */
    public static Integer findOddTimesNum(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }

        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        return eor;
    }


    /*
     * 以下为对数器，用于测试
     * */

    public static Integer comparator(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }

        Set<Integer> keySet = map.keySet();
        for (Integer key : keySet) {
            if ((map.get(key) & 1) == 1) {
                return key;
            }
        }
        return null;
    }

    /**
    * 生成符合要求的测试数据，一个数出现奇数次，其余出现偶数次
    */
    public static int[] generateEvenAndOddArr(int maxTimes, int numKinds, int maxValue) {

        int times = (int) (Math.random() * maxTimes + 1);
        //1个数出现的奇数次
        int oddTimes = (times & 1) == 0 ? times - 1 : times;
        //剩下的偶数次数的种数
        int[] evenTimes = new int[numKinds - 1];

        //生成数组的长度
        int length = oddTimes;

        //出现偶数次的每种数,出现的偶数次
        for (int i = 0; i < evenTimes.length; i++) {
            do {
                evenTimes[i] = (int) (Math.random() * maxTimes + 1);
            } while ((evenTimes[i] & 1) == 1);
            length += evenTimes[i];
        }
        int[] ans = new int[length];
        //出现奇数次的数
        int oddNum = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
        // 先把生成的出现奇数次的数放入ans数组

        int i = 0;
        while (i < oddTimes) {
            ans[i++] = oddNum;
        }

        //把出现偶数次的数放入ans数组
        for (int i1 = 0; i1 < evenTimes.length; i1++) {
            int evenNum = oddNum + (int) (Math.random() * maxValue + 1);
            for (int j = i; j < i + evenTimes[i1]; j++) {
                ans[j] = evenNum;
            }
            i = i + evenTimes[i1];
        }

        for (int j = 0; j < length; j++) {
            int temp = ans[j];
            int index = (int) (Math.random() * length);
            ans[j] = ans[index];
            ans[index] = temp;
        }

        return ans;
    }

    public static void prinArr(int[] arr) {
        if (arr == null || arr.length < 1) {
            return;
        }
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

题目三：怎么把一个int类型的数，提取出最右侧的1来

     /**
     * 一个int类型的数，提取出二进制最右侧的1
     *
     * @param num
     */
    public static int nearRightOne(int num) {
        return num & (~num + 1);
    }

    /**
     * 打印一个数的二进制位信息
     *
     * @param num
     */
    public static void printByte(int num) {
        for (int i = 31; i >= 0; i--) {
            System.out.print((num >> i) & 1);
        }
    }

题目4：一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数

    /**
     * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
     *
     * @param arr
     */
    public static List<Integer> evenTimesOddTimes2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return null;
        }
        //假设2个奇数次的数为a和b，eor =a^b
        int eor = 0;
        for (int i : arr) {
            eor ^= i;
        }
        //a!=b,则eor>0,eor1为eor二进制最右侧的1
        int eor1 = eor & (~eor + 1);
        int ans1 = 0;
        for (int i : arr) {
            if ((i & eor1) == 0) {
                ans1 = ans1 ^ i;
            }
        }
        List<Integer> ans = new ArrayList<>(2);
        ans.add(ans1);
        ans.add(ans1 ^ eor);
        return ans;
    }

题目5：一个数组中有一种数出现K次，其他数都出现了M次，M > 1, K < M找到，出现了K次的数，要求，额外空间复杂度O(1)，时间复杂度O(N)

    /**
     * 一个数组中有一种数出现K次，其他数都出现了M次，
     * M > 1,  K < M
     * 找到，出现了K次的数，
     * 要求，额外空间复杂度O(1)，时间复杂度O(N)
     *
     * @param arr
     * @return
     */
    public static Integer kTimesNum(int[] arr, int k, int m) {
        if (arr == null || arr.length < 3) {
            return null;
        }

        int length = 32;
        int[] bytes = new int[length];
        for (int i = 0; i < length; i++) {
            for (int num : arr) {
                bytes[i] += (num >> i) & 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < length; i++) {
            if ((bytes[i] % m) == k) {
                ans |= (1 << i);
            }
        }
        return ans;
    }