Medium

题目描述

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

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

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

解题思路

这道题要求在 O(log n) 时间内找到只出现一次的元素，提示我们使用二分查找。

关键观察：在单一元素出现之前，数组中的元素都是成对出现的。如果我们观察索引位置，会发现一个重要规律：

  • 在单一元素之前：第一个重复元素总是出现在偶数索引位置，第二个重复元素出现在奇数索引位置
  • 在单一元素之后：这个规律被打破，第一个重复元素出现在奇数索引位置

利用这个规律，我们可以用二分查找：

  1. 取中间位置 mid
  2. 如果 mid 是奇数，我们检查 nums[mid] 和 nums[mid-1] 是否相等
  3. 如果 mid 是偶数，我们检查 nums[mid] 和 nums[mid+1] 是否相等
  4. 根据比较结果决定在左半部分还是右半部分继续搜索

为了简化逻辑，我们可以统一处理：如果 mid 是奇数就减 1，确保 mid 总是偶数，然后比较 nums[mid] 和 nums[mid+1]。

推荐解法：二分查找法，时间复杂度 O(log n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 确保 mid 是偶数
            if (mid % 2 == 1) {
                mid--;
            }
            
            // 如果 nums[mid] == nums[mid + 1]，说明单一元素在右边
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2;
            } else {
                // 否则单一元素在左边（包括 mid 位置）
                right = mid;
            }
        }
        
        return nums[left];
    }
};

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            # 确保 mid 是偶数
            if mid % 2 == 1:
                mid -= 1
            
            # 如果 nums[mid] == nums[mid + 1]，说明单一元素在右边
            if nums[mid] == nums[mid + 1]:
                left = mid + 2
            else:
                # 否则单一元素在左边（包括 mid 位置）
                right = mid
        
        return nums[left]

public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        int left = 0, right = nums.Length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 确保 mid 是偶数
            if (mid % 2 == 1) {
                mid--;
            }
            
            // 如果 nums[mid] == nums[mid + 1]，说明单一元素在右边
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2;
            } else {
                // 否则单一元素在左边（包括 mid 位置）
                right = mid;
            }
        }
        
        return nums[left];
    }
}

var singleNonDuplicate = function(nums) {
    let left = 0, right = nums.length - 1;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        
        if (mid % 2 === 1) mid--;
        
        if (nums[mid] === nums[mid + 1]) {
            left = mid + 2;
        } else {
            right = mid;
        }
    }
    
    return nums[left];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)二分查找，每次排除一半的搜索空间
空间复杂度O(1)只使用了常数级别的额外空间