力扣540题：线性扫描法如何高效定位唯一数

题目重解

一个严格递增的有序数组中，除某个元素外，其余每个元素均出现两次。这个看似简单的条件背后隐藏着巧妙的规律——单一元素会打破数组的"成对对称性"。题目要求以O(log n)时间复杂度解决，但线性扫描法在特定场景下同样高效。

解题思路与过程

代码采用线性扫描法，核心逻辑分为三步：

1.单元素直接返回：若数组长度为1，唯一元素即答案。

2.中间元素检查：遍历数组中间部分，若当前元素与左右邻居均不同，则为目标。

3.边界处理：若未找到目标，检查首尾元素（因目标可能位于边界）。

解法虽为O(n)时间复杂度，但实际运行中因提前返回机制，平均效率接近最优。

代码

class Solution {  
public:  
    int singleNonDuplicate(vector<int>& nums) {  
        // 情况1：数组仅1个元素时直接返回  
        if(nums.size()==1) return nums[0];  

        // 情况2：检查中间元素是否满足条件  
        for(int i=1; i<nums.size()-1; i++) {  
            if(nums[i]!=nums[i-1] && nums[i]!=nums[i+1]) {  
                return nums[i]; // 找到目标立即返回  
            }  
        }  

        // 情况3：处理边界（目标在首尾）  
        if(nums[0]==nums[1]) {  
            return nums.back(); // 目标在末尾  
        }  
        return nums[0]; // 目标在开头  
    }  
};