解法一：异或

1、思路

两个相同数字的异或结果为0，所以遍历数组，把所有元素都异或起来，剩下的就是只出现一次的数字了。
时间复杂度为$O(N)$。

2、代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int res = 0;

        for (int& num : nums) res ^= num;

        return res;
    }
};

解法二：二分

1、思路

有序数组应该首先考虑二分，相同元素是成对出现的，我们要找的是第一个不成对的元素。这里可以用一个异或的技巧来找到同一对元素：

• 若mid为偶数，则mid ^ 1为奇数，是当前元素对的前一个元素；

• 若mid为奇数，则mid ^ 1为偶数，是当前元素对的后一个元素。

2、代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;

        while (left < right)
        {
            int mid = left + (right - left) / 2;    // 防int溢出的写法，等同于(left + right) / 2
            if (nums[mid] == nums[mid ^ 1])         //当前元素对相同，则不同元素对肯定在后面
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }

        return nums[left];
    }
};