琼海建设网站,改变网站的域名,织梦手机网站怎么安装教程视频,专业做网站流程LeetCode双指针#xff1a;有序数组中的单一元素
题目描述
给你一个仅由整数组成的有序数组#xff0c;其中每个元素都会出现两次#xff0c;唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复…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先进行假设 若mid为奇数判断它和它前一个是否相等相等则左指针调整 若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%20){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 bnew 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]mid3为奇数将2和1进行异或 01 ^ 11 10即十进制中的 2那么不正是相当于对其进行了减一操作
同理当mid2时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}));}
}
