LeetCode双指针：有序数组中的单一元素

Lee tCo de 双指针：有序数组中的单一元素

题目 描述

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

解题 思路

由有序数组，以及要求 O(log n) 时间复杂度和 O(1) 空间复杂度得知需使用二分查找，怎么找？考虑到它的总数一定是为奇数，那么就可以从左右两边每次划分后的数量进行查找，怎么判别获得中间值之后知道哪一边是几十个哪一边是偶数个？这个我用的笨方法：举例

1、[1,1,2,3,3,4,4]右指针为6，左指针为0，除以2之后mid为3（奇数）落在第一个3上，根据预想需要调整右指针到第二个3上
2、[1,1,2,2,3,3,4]右指针为6，左指针为0，除以2之后mid为3（奇数）落在第二个2上，根据预想需要调整左指针到第一个2上
3、[1,2,2,3,3]右指针为4，左指针为0，除以2之后mid为2（偶数）落在第二个2上，根据预想需要调整右指针到第二个2上
4、[1,1,2,2,3]右指针为4，左指针为0，除以2之后mid为2（偶数）落在第一个2上，根据预想需要调整左指针到第一个2上

可能此种解释比较麻烦，我也没找到让自己和解的方法，仅代表我自己的理解

接下来就是进行归类，我把需要移动左指针的进行归类（1,3）先进行假设：

1. 若mid为奇数判断它和它前一个是否相等，相等则左指针调整
1. 若m id为偶数判断它和它后一个是否相等，相等则左指针调整

带入2,4情况，发现符合，可以试试找规律，自己推出来较为容易理解，上述也可以不知道这一种选择，改变判等的位置，相应更改后边即可

代码

public class BinSearch3 {
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low &lt; high) {
            int mid = (high - low) / 2 + low;
            //若mid为偶数判断它和它后一个是否相等，相等则左指针调整
            if (mid%2==0){
                if (nums[mid] == nums[mid + 1]){
                    low = mid + 1;
                }else {
                    high = mid;
                }
                //若mid为奇数判断它和它前一个是否相等，相等则左指针调整
            }else {
                if (nums[mid] == nums[mid - 1]){
                    low = mid + 1;
                }else {
                    high = mid;
                }
            }

        }
        return nums[low];
    }

    public static void main(String[] args) {
        BinSearch3 b=new BinSearch3();
        System.out.println(b.singleNonDuplicate(new int[]{1,1,2,3,3,4,4}));
    }
}

代码优化

如上，判定奇偶情况代码十分臃肿，冗余，对其进行进一步改进，此时需要了解^的使用

位运算的异或操作符 ^。二进制中，异或有一个有趣的性质，即 a ^ b 在 a 和 b 不相同时结果为 1，相同时结果为 0。

1 ^ 3 的结果是 01 ^ 11 = 10，即十进制中的 2。

带入上述例子[1,1,2,2,3,3,4]mid=3，为奇数将2和1进行异或 01 ^ 11 = 10即十进制中的 2那么不正是相当于对其进行了减一操作

同理，当mid=2时，01 ^ 10 = 11即十进制中的 3那么不正是相当于对其进行了加一操作

因此对其进行优化后：

public class BinSearch3 {
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low &lt; high) {
            int mid = (high - low) / 2 + low;
            if (nums[mid] == nums[mid ^ 1]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
    public static void main(String[] args) {
        BinSearch3 b = new BinSearch3();
        System.out.println(b.singleNonDuplicate(new int[]{1, 1, 2, 3, 3, 4, 4, 8, 8}));
    }
}