有序数组中的单一元素（二）

解决方案

方法一：暴力法

我们可以使用线性搜索来检查数组中的每个元素，直到找到单个元素。

算法：

• 从第一个元素开始，我们检查每个第二个元素是否与当前元素相同。如果不同，说明该元素是单个元素。
• 如果我们到达最后一个元素，则它为单一元素。

Java 实现

class Solution { public int singleNonDuplicate(int[] nums) { for (int i = 0; i < nums.length - 1; i+=2) { if (nums[i] != nums[i + 1]) { return nums[i]; } } return nums[nums.length - 1]; } }

Python 实现

def singleNonDuplicate(self, nums: List[int]) -> int: for i in range(0, len(nums) - 2, 2): if nums[i] != nums[i + 1]: return nums[i] return nums[-1]

C++ 实现

class Solution { public: int singleNonDuplicate(vector<int>& nums) { for (int i = 0; i < nums.size() - 1; i += 2) { if (nums[i] != nums[i + 1]) { return nums[i]; } } return nums.back(); } };

复杂度分析

时间复杂度：O(n)。我们的线性搜索只查看每个元素一次。

空间复杂度：O(1)，只使用了常数的额外空间。

尽管这个解决方案可行，但是问题中要求我们使用时间复杂度在 O(log n) 的解决方案。因此，该解决方案还不够好。