Skip to content

540. Single Element in a Sorted Array

Description

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

 

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

Solutions

The given array $\textit{nums}$ is sorted, and we need to find the element that appears only once in $\textit{O}(\log n)$ time. Therefore, we consider using binary search to solve this problem.

We define the left boundary of the binary search as $\textit{l} = 0$ and the right boundary as $\textit{r} = n - 1$, where $n$ is the length of the array.

In each step, we take the middle position $\textit{mid} = (l + r) / 2$. If the index $\textit{mid}$ is even, we should compare $\textit{nums}[\textit{mid}]$ with $\textit{nums}[\textit{mid} + 1]$. If the index $\textit{mid}$ is odd, we should compare $\textit{nums}[\textit{mid}]$ with $\textit{nums}[\textit{mid} - 1]$. Therefore, we can uniformly compare $\textit{nums}[\textit{mid}]$ with $\textit{nums}[\textit{mid} \oplus 1]$, where $\oplus$ denotes the XOR operation.

If $\textit{nums}[\textit{mid}] \neq \textit{nums}[\textit{mid} \oplus 1]$, then the answer is in $[\textit{l}, \textit{mid}]$, so we set $\textit{r} = \textit{mid}$. If $\textit{nums}[\textit{mid}] = \textit{nums}[\textit{mid} \oplus 1]$, then the answer is in $[\textit{mid} + 1, \textit{r}]$, so we set $\textit{l} = \textit{mid} + 1$. We continue the binary search until $\textit{l} = \textit{r}$, at which point $\textit{nums}[\textit{l}]$ is the element that appears only once.

The time complexity is $\textit{O}(\log n)$, where $n$ is the length of the array $\textit{nums}$. The space complexity is $\textit{O}(1)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] != nums[mid ^ 1]:
                r = mid
            else:
                l = mid + 1
        return nums[l]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] != nums[mid ^ 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] != nums[mid ^ 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func singleNonDuplicate(nums []int) int {
    l, r := 0, len(nums)-1
    for l < r {
        mid := (l + r) >> 1
        if nums[mid] != nums[mid^1] {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return nums[l]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function singleNonDuplicate(nums: number[]): number {
    let [l, r] = [0, nums.length - 1];
    while (l < r) {
        const mid = (l + r) >> 1;
        if (nums[mid] !== nums[mid ^ 1]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return nums[l];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
        let mut l = 0;
        let mut r = nums.len() - 1;
        while l < r {
            let mid = (l + r) >> 1;
            if nums[mid] != nums[mid ^ 1] {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        nums[l]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int singleNonDuplicate(int* nums, int numsSize) {
    int l = 0, r = numsSize - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (nums[mid] != nums[mid ^ 1]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return nums[l];
}

Comments