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

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

题目描述

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

请你找出并返回只出现一次的那个数。

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

示例 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为奇数判断它和它前一个是否相等，相等则左指针调整
• 2. 若mid为偶数判断它和它后一个是否相等，相等则左指针调整

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

代码

public class BinSearch3 {public int singleNonDuplicate(int[] nums) {int low = 0, high = nums.length - 1;while (low < 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 < 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}));}
}