关于有序数组找唯一元素算法的时间复杂度及LeetCode提交疑问

1. 你的代码时间复杂度确实是O(n) #

没错，你写的这段代码时间复杂度就是O(n)。原因很简单：你用了一个for循环遍历数组的每一个元素，数组长度为n时，循环会执行n次，而每次循环里的异或操作r = r ^ nums[i]是常数时间O(1)的操作，所以整体时间复杂度是线性的O(n)，和你的判断完全一致。

2. 为什么LeetCode会接受你的O(n)解法？ #

LeetCode的判题逻辑并不是完全严格按照题目给出的复杂度要求来卡的，主要看代码的实际运行时间是否在设定的阈值内，这里有几个关键点：

• 异或操作的高效性：异或是非常轻量的位运算，执行速度极快。哪怕数组长度达到10^5甚至更大，这段代码的实际运行时间也可能远低于题目设定的时间限制（比如1秒），所以能顺利通过所有测试用例。
• 空间复杂度符合要求：你的代码只使用了一个额外变量r，空间复杂度是O(1)，完全满足题目对空间的要求。
• 测试用例规模限制：有时候LeetCode的测试用例并没有设置极端大的输入，比如没有让n大到足以让O(n)解法超时的程度，所以你的代码能轻松跑过。

附：符合O(logn)要求的二分查找解法 #

既然题目要求O(logn)的时间复杂度，这里给你一个用二分查找实现的解法，供参考：

public static int singleNonDuplicate(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        // 保证mid是偶数，这样可以和mid+1配对
        if (mid % 2 == 1) {
            mid--;
        }
        // 如果当前配对相等，说明唯一元素在右边
        if (nums[mid] == nums[mid + 1]) {
            left = mid + 2;
        } else {
            // 否则在左边
            right = mid;
        }
    }
    return nums[left];
}

这个解法利用了数组有序且除了唯一元素外都是成对出现的特性，通过二分查找每次缩小一半范围，时间复杂度是O(logn)，空间复杂度O(1)，完全符合题目要求。

内容的提问来源于stack exchange，提问作者user5759526