【刷题篇】详解异或符 && 打破对二分的刻板认知

文章目录

• 1. 找单身狗1.0版本
• 2. 找单身狗2.0版本
• 3. 在一个有序数组中，找 >= 某个数最左侧的位置
• 4. 局部最小值问题

今天开始就要进入 数据结构和算法篇 啦，今天先带来 两道位运算和两道二分的题 ，让你通过这两道题彻底迷上算法入门算法~~🎉🎉🎉

1. 找单身狗1.0版本

已知在一个整型数组中，只有一种数出现了奇数次，其他的所有数都出现了偶数次（即只有一种数落单，其他数都成双成对），请你找出这个只出现了奇数次的数字（找出这个单身狗🐕）。

这道题有一个最快速的方法 --> 异或^。

我们首先要知道，异或是满足交换律和结合律的，并且任何数和它本身异或都是0，任何数和0异或都是它本身，只有一种数出现了奇数次，其他的数都出现了偶数次，那我们就可以抽象出 只有一个数字单独出现了一次，其他数字都出现了偶数次。

我们就可以把所有数都异或到一起，例如 ‘4’ 出现了4次，那么把 ‘4’ 异或四次结果就是0，所有成双的数异或到一起最终的结果就是0，剩下的单身狗和0异或依然是它本身，这样我们就找到了这个单身🐕。

代码如下：

public class TestDemo {
    public static void main(String[] args) {
        int[] arr = {1,1,2,2,3,3,4,4,4,5,5,6,6};//4就是单身狗
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];//eor最终的值就是我们要的结果
        }
        System.out.println(eor);
    }
}

//输出结果：
4

---

🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉

2. 找单身狗2.0版本

上道题还是非常简单的，在其基础上我们加强一下。

仍然已知在一个整型数组中，有两种数出现了奇数次，其他所有的数都出现了偶数次。请你找出这两个孤独的单身🐕。

这道题和上道题唯一的不同就是， 有 两 个 只 出 现 了 奇 数 次 的 数 字 ， \color{BlueViolet}有两个只出现了奇数次的数字， 有两个只出现了奇数次的数字，我们依然可以使用异或来解决这道题，假设这两个数是 a 和 b，把他们都异或到一起发现最终的结果是a ^ b，a ^ b 的结果显然是一个全新的值，并不是我们想要的，我们又不可能再把这个值再还原回去，那么该如何做呢？

试想一下，既然 a 和 b 是两个不同的数，那他们a ^ b 一定不等于0，假设a ^ b = c，那么 c 的32位二进制上，一定有某一位为1，如果 c 的比特位全是0，那 c 就一定等于0，所以上述推论是成立的。

因此我们就可以想出一种很奇妙的解法——分组。假设 c 的第 k 位是1，把所有第 k 位是 1 的分到一组，所有第 k 位是 0 的分到一组，这样就可以把 a 和 b 分开（既然 c 的第 k 位是 1，说明 a 和 b的第 k 位一定不相等），第一组异或在一起的结果是 a，第二组异或在一起的结果就是 b。为了得到第k位，我们依然要先让所有的数都异或在一起得到 eor = a ^ b，这样我们就可以通过运算得到 c 的第k位。既然我们已经得到了a ^ b，只要再得到 eor1 = a（其中一组的异或结果），再让 eor1 ^ eor（a ^ b ^ a）就可以得到 b，就可以减少运算。

代码如下：

public static void main(String[] args) {
        int[] arr = {1,1,2,2,3,3,4,4,5,6};
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // eor = a ^ b
        // eor != 0
        // eor的二进制中必有一位是1
        //此处我们默认取eor最右边的1
        //eor & (~eor + 1) 常用的计算技巧 —> 取出二进制中最右边的1，不信可以自己用几个数验证是否能取到最右边的1
        int rightOne = eor & (~eor + 1);
        int onlyOne = 0;//eor1
        //把第k位是1和第k位是0的分为两组
        for (int i = 0; i < arr.length; i++) {
            //第k位是0的一组
            if((rightOne & arr[i]) == 0) {
                onlyOne ^= arr[i];//onlyOne是 a 或 b
            }
        }
        System.out.println(onlyOne + " " + (onlyOne ^ eor));
    }

//运行结果:
6 5

---

🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉

3. 在一个有序数组中，找 >= 某个数最左侧的位置

假设有一个数组1、1、1、2、2、3、3、3、3、4、4、5，我们要找的数是 3，那么我们的任务就是找到 3 第一次在数组中出现的位置。

当然，最容易想到的方式还是暴力的遍历数组，但是这样的时间复杂度是O(N^2)，如果你在面试时这样写代码，恐怕面试官就会让你出门左转了。

二分查找可以有效的把时间复杂度降到O(logN)，我们如何把这道题与二分查找联系起来呢？我们要时刻牢记二分查找的实质，每查找一次就可以抛弃一半的数据，既然是有序数组，我们就可以尝试用二分查找。

传统二分查找，找到要找的数了就退出，该二分查找要一直二分直到结束，最后 t 标记的位置就是我们要找的位置。

代码如下：

//找 >= 某个数最左侧的位置
    public static int findLeft(int[] arr, int k) {
        int l = 0;
        int r = arr.length - 1;
        //标记
        int t = 0;
        while(l <= r) {
        	//这种写法是为了防止溢出
        	//等同于 (l + r) / 2
            int mid = l + ((r - l) >> 1);
            if(arr[mid] >= k) {
            	//缩小范围
                r = mid - 1;
                //更新标记
                t = mid;
            } else {
                l = mid + 1;
            }
        }
        return t;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,1,2,2,3,3,3,3,4,4,5,5};
        int k = 3;
        int ret = findLeft(arr, k);
        System.out.println(ret);
    }

//运行结果：
5

---

🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉🎉

4. 局部最小值问题

已知在一个无序的整型数组arr中，相邻的两个数一定不相等，求局部最小值。
局部最小值的定义：若是0下标的数，只要arr[0] < arr[1]，那么arr[0]就是局部最小；若是arr.length-1下标的数，只要arr[length - 1] < arr[length - 2]，那么arr[length - 1]就是局部最小；若是arr[i] < arr[i - 1] && arr[i] < arr[i + 1]，那么arr[i]就是局部最小

这道题依然可以用二分的思想来解，我们印象中使用二分的前提是有序，但是这种印象其实是错误的，即使是无序的数组中，也依然可以使用二分。

假设数组长度为N，由下面图可知，如果0和N-1不是局部最小，那么0~N-1区间内一定存在局部最小，因为 这样的两段线，无论怎么连，都一定存在一个拐点，也就是局部最小值。同理，如果M不是局部最小，不妨设它比M-1要大，那么一定也是如图所示的趋势，0到M-1区间内一定存在局部最小，就可以继续二分，直到找到局部最小值。

代码如下：

//局部最小值问题
    public static int findLocalMinimum(int[] arr) {
        int l = 0;
        int r = arr.length - 1;
        //先判断两边的数，如果相等直接返回
        if(arr[l] < arr[l + 1]) {
            return l;
        } else if(arr[r] < arr[r - 1]) {
            return r;
        }

        while(l <= r) {
            int mid = l + ((r - l) >> 1);
            if(arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else if (arr[mid] > arr[mid - 1]) {
                r = mid - 1;
            } else { // 因为相邻的数一定不相等，所以只剩中间小于右边的情况
                l = mid + 1;
            }
        }
        //找不到
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {9,6,7,8,5,10,12};
        int ret = findLocalMinimum(arr);
        System.out.println(ret);
    }

//运行结果：
1