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

Categories:

题目描述
思路分析
1. 解法一：二分查找（下标成对）（推荐）
相似题目

题目描述

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

思路分析

解法一：二分查找（下标成对）（推荐）

核心思路：

有序数组中除一个元素外，其余元素成对出现。

将 mid 调整为偶数下标，若 nums[mid] == nums[mid+1]，说明单一元素在右侧，否则在左侧。

二分直到 left == right。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度。

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

// 二分定位单一元素
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) {
                mid--;
            }
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

// 二分定位单一元素
func singleNonDuplicate(nums []int) int {
	left, right := 0, len(nums)-1

	for left < right {
		mid := left + (right-left)/2
		if mid%2 == 1 {
			mid--
		}
		if nums[mid] == nums[mid+1] {
			left = mid + 2
		} else {
			right = mid
		}
	}

	return nums[left]
}

相似题目

题目	难度	考察点
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找
153. 寻找旋转排序数组中的最小值	中等	二分查找
162. 寻找峰值	中等	二分查找
81. 搜索旋转排序数组 II	中等	二分查找
704. 二分查找	简单	二分查找
852. 山脉数组的峰顶索引	简单	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/00553978