LC 540. 有序数组中的单一元素

题目描述

这是 LeetCode 上的 540. 有序数组中的单一元素 ，难度为 中等。

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

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

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

提示:

• $1 <= nums.length <= 10^5$
• $0 <= nums[i] <= 10^5$

---

遍历

数据范围为 $10^5$，最简单的方法是以「步长为 $2$」的方式进行从前往后的遍历，找到第一个不符合「与后一个数相等」条件的值即是答案。

或是利用单个元素只有一个（其余成对出现），从头到尾异或一遍，最终结果为单一元素值。

代码：

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(1)$

---

二分

这道题的「二段性」分析需要一点点「脑筋急转弯」。

由于给定数组有序 且 常规元素总是两两出现，因此如果不考虑“特殊”的单一元素的话，我们有结论：成对元素中的第一个所对应的下标必然是偶数，成对元素中的第二个所对应的下标必然是奇数。

然后再考虑存在单一元素的情况，假如单一元素所在的下标为 $x$，那么下标 $x$ 之前（左边）的位置仍满足上述结论，而下标 $x$ 之后（右边）的位置由于 $x$ 的插入，导致结论翻转。

存在这样的二段性，指导我们根据当前二分点 $mid$ 的奇偶性进行分情况讨论：

• $mid$ 为偶数下标：根据上述结论，正常情况下偶数下标的值会与下一值相同，因此如果满足该条件，可以确保 $mid$ 之前并没有插入单一元素。正常情况下，此时应该更新 $l = mid$，否则应当让 $r = mid - 1$，但需要注意这样的更新逻辑，会因为更新 $r$ 时否决 $mid$ 而错过答案，我们可以将否决 $mid$ 的动作放到更新 $l$ 的一侧，即需要将更新逻辑修改为 $l = mid + 1$ 和 $r = mid$ ；

• $mid$ 为奇数下标：同理，根据上述结论，正常情况下奇数下标的值会与上一值相同，因此如果满足该条件，可以确保 $mid$ 之前并没有插入单一元素，相应的更新 $l$ 和 $r$。

代码：

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(1)$

---

二分（异或技巧）

不难发现，上述解法对奇偶下标的分情况讨论仅在于当前值 $nums[i]$ 是与 $nums[i + 1]$（当 $i$ 为偶数时）还是 $nums[i - 1]$（当 $i$ 为奇数时）进行比较。

而这样的「连续段 偶奇 两两成对」的组合，适合使用「异或」来找相应的成组对象。

实际上，该技巧广泛地应用在图论存图中：使用邻接表（链式向前星）存无向图时，直接访问「当前边 $e$」所对应的「反向边 $e’$」。这也是为什么在「链式向前星」中我们只需要使用「单链表」并设定 $idx$ 从 $0$ 开始进行存图即可：能够满足遍历所有出边，同时如果有访问相应反向边的需求，只需要通过 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(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.540 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。