前言

本次要进行分析的题目有两个。为什么要一起讲呢？主要是最终我想到的解题思路甚至是解题方法都是一样的

本次要进行解析的题目：

• 有序数组中的单一元素
• 只出现一次的数字

有序数组中的单一元素

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

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

你设计的解决方案必须满足 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

解题思路

因为是有序数组且重复的元素就会出现两次，所以我们可以以两个数据为间隔，每次判断当前的 index和index+1时候的值是否相等

function singleNonDuplicate(nums: number[]): number {
    for(let i = 0; i < nums.length; i+=2) {
        if (nums[i] != nums[i + 1]) {
            return nums[i]
        }
    }
};

接下来的一个解题思路和 136. 只出现一次的数字 这题的折腾方法一模一样，等会一起说！

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解题思路

上面我们也说了，这两个的解题思路甚至可以是一样的，主要使用什么方法呢？

异或算法

• 两个相同的数异或返回的结果是 0
• 0 异或任何数返回的结果都是那个数
• 同时异或满足交换律，分配律
• 因此也就是说 A ⊕ A = 0 ,0 ⊕ A = A, A ⊕ B ⊕ A = B
• 因此要找到那个单独的数，我们只需要遍历异或就可以了，这样每两个相同的数异或为 0 ，最后就是 0 和那个单独的数异或，得到那个数

function singleNumber(nums: number[]): number {
    for(let i = 1; i< nums.length; i++) {
        nums[0] = nums[0] ^ nums[i]
    }
    return nums[0]
};

当然 还可以写成这样：

function singleNumber(nums) {
    return nums.reduce((pre, cur) => pre ^ cur);
};

reduce 方法实现的原理也是异或，我们只是利用它的 API 特性，它刚好能够简化我们的代码