题目描述
这是 LeetCode 上的 540. 有序数组中的单一元素 ，难度为 中等。
Tag : 「二分」、「异或」
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(\log n)O(logn) 时间复杂度和 O(1)O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8] 输出: 2 复制代码
示例 2:
输入: nums = [3,3,7,7,10,11,11] 输出: 10 复制代码
提示:
- 1 <= nums.length <= 10^51<=nums.length<=105
- 0 <= nums[i] <= 10^50<=nums[i]<=105
遍历
数据范围为 10^5105，最简单的方法是以「步长为 22」的方式进行从前往后的遍历，找到第一个不符合「与后一个数相等」条件的值即是答案。
或是利用单个元素只有一个（其余成对出现），从头到尾异或一遍，最终结果为单一元素值。
代码：
class Solution { public int singleNonDuplicate(int[] nums) { int n = nums.length; for (int i = 0; i < n - 1; i += 2) { if (nums[i] != nums[i + 1]) return nums[i]; } return nums[n - 1]; } } 复制代码
class Solution { public int singleNonDuplicate(int[] nums) { int ans = 0; for (int i : nums) ans ^= i; return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(1)O(1)
二分
这道题的「二段性」分析需要一点点「脑筋急转弯」。
由于给定数组有序 且 常规元素总是两两出现，因此如果不考虑“特殊”的单一元素的话，我们有结论：成对元素中的第一个所对应的下标必然是偶数，成对元素中的第二个所对应的下标必然是奇数。
然后再考虑存在单一元素的情况，假如单一元素所在的下标为 xx，那么下标 xx 之前（左边）的位置仍满足上述结论，而下标 xx 之后（右边）的位置由于 xx 的插入，导致结论翻转。
存在这样的二段性，指导我们根据当前二分点 midmid 的奇偶性进行分情况讨论：
- midmid 为偶数下标：根据上述结论，正常情况下偶数下标的值会与下一值相同，因此如果满足该条件，可以确保 midmid 之前并没有插入单一元素。正常情况下，此时应该更新 l = midl=mid，否则应当让 r = mid - 1r=mid−1，但需要注意这样的更新逻辑，会因为更新 rr 时否决 midmid 而错过答案，我们可以将否决 midmid 的动作放到更新 ll 的一侧，即需要将更新逻辑修改为 l = mid + 1l=mid+1 和 r = midr=mid ；
- midmid 为奇数下标：同理，根据上述结论，正常情况下奇数下标的值会与上一值相同，因此如果满足该条件，可以确保 midmid 之前并没有插入单一元素，相应的更新 ll 和 rr。
代码：
class Solution { public int singleNonDuplicate(int[] nums) { int n = nums.length; int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (mid % 2 == 0) { if (mid + 1 < n && nums[mid] == nums[mid + 1]) l = mid + 1; else r = mid; } else { if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) l = mid + 1; else r = mid; } } return nums[r]; } } 复制代码
- 时间复杂度：O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)
二分（异或技巧）
不难发现，上述解法对奇偶下标的分情况讨论仅在于当前值 nums[i]nums[i] 是与 nums[i + 1]nums[i+1]（当 ii 为偶数时）还是 nums[i - 1]nums[i−1]（当 ii 为奇数时）进行比较。
而这样的「连续段 偶奇 两两成对」的组合，适合使用「异或」来找相应的成组对象。
实际上，该技巧广泛地应用在图论存图中：使用邻接表（链式向前星）存无向图时，直接访问「当前边 ee」所对应的「反向边 e'e′」。这也是为什么在「链式向前星」中我们只需要使用「单链表」并设定 idxidx 从 00 开始进行存图即可：能够满足遍历所有出边，同时如果有访问相应反向边的需求，只需要通过 e[i^1] 访问。
对这种存图方式不熟悉的同学，可以看前置 🧀：涵盖所有的「存图方式」与「最短路算法（详尽注释）」。
代码：
class Solution { public int singleNonDuplicate(int[] nums) { int n = nums.length; int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] == nums[mid ^ 1]) l = mid + 1; else r = mid; } return nums[r]; } } 复制代码
- 时间复杂度：O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.540 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
