题目大意：
有序数组中的单一元素
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8] 输出: 2
示例 2:
输入: [3,3,7,7,10,11,11] 输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=540
解题思路分析：
这道题的解题方式有很多，比如我们循环一遍数组，然后使用HashMap来记录每种数字出现的个数，最后查看数字个数为1的即是答案。不过题目要求我们使用O(1)的空间复杂度来解题，因此HashMap方式并不推荐。
另一种相对简单的解题方式是两两比较数组中的数字，因为数组已经升序排列好，因此，从首位开始每相邻的两个数字应该是相同的，当出现不相同的数字时，这两个数字中下标较小的一个即是结果。
我个人最为推荐的是使用位运算的方式来解本题，实际上本题是异或运算的经典使用场景。Leetcode的题库中也有类似的题目：LEETCODE 136. Single Number 解题思路分析，与本题的描述几乎完全一致。
回到本题，我们首先回顾一下异或的基本概念。相同两数的异或结果为0，而0和任何数的异或结果都是那个任意的数字。因此，本题中所有相同的数字之间的异或结果都是0，0与那个单一元素的异或结果即是那个单一元素，也是本题的解。由于异或运算是符合交换法的，也就是说数组中这些数字的异或执行顺序并不会影响最终结果，因此本题中给定的数组即使没有排序，也不会影响我们使用异或运算来解题。
实现代码：
public int singleNonDuplicate(int[] nums) {
int res=0;
for(int n : nums) res^=n;
return res;
} 本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Element in a Sorted Array.
Memory Usage: 39.8 MB, less than 8.00% of Java online submissions for Single Element in a Sorted Array.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-540-single-element-in-a-sorted-array-解题思路分析/