540.Single Element in a Sorted Array

tags: `Medium`,`Array`,`Binary Search`

題目描述

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 <= 10⁵
0 <= nums[i] <= 10⁵

解答

C++

















class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int L = 0, R = nums.size() - 1;
        while (L < R) {
            int M = (L + R) / 2;
            if (nums[M] == nums[M-1]) {
                if ((M - L) & 1) L = M + 1;
                else R = M - 2;
            } else {
                if ((M - L) & 1) R = M - 1;
                else L = M;
            }
        }
        return nums[L];
    }
};

Yen-Chi ChenTue, Feb 21, 2023

Python












class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        L, R = 0, len(nums) - 1
        while L < R:
            M = (L + R) // 2
            if nums[M] == nums[M-1]:
                if (M - L) & 1: L = M + 1
                else: R = M - 2
            else:
                if (M - L) & 1: R = M - 1
                else: L = M
        return nums[L]

Yen-Chi ChenTue, Feb 21, 2023













class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            m = l + (r - l) // 2
            n = m - 1 if m % 2 else m + 1
            if nums[m] != nums[n]:
                r = m
            else:
                l = m + 1

        return nums[l]

Ron ChenWed, Feb 22, 2023

Javascript

思路：

因為只有一個數字出現一次，所以nums.length一定是奇數，做binary search切下去剛好就是正中間。
i = (0 + nums.length - 1) / 2

i為奇數
nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
前後的數字數量為偶數，如果nums[i] == nums[i-1]，那前面剩下的數量就是奇數，一定會有一個數字落單，所以要找的數字就在i前面，反之亦然。
i為偶數
nums = [3, 3, 7, 7, 10, 11, 11]
前後的數字數量為奇數，如果nums[i] == nums[i-1]，那前面剩下的數量就是偶數，那要找的數字就在i後面了。


























function singleNonDuplicate(nums) {
  let max = nums.length - 1;
  let min = 0;
  while (max >= min) {
    const mid = ~~((max + min) / 2);
    if (nums[mid] !== nums[mid + 1] && nums[mid] !== nums[mid - 1]) {
      return nums[mid];
    }

    if (mid % 2 === 0) {
      if (nums[mid] === nums[mid + 1]) {
        min = mid + 1;
      }
      if (nums[mid] === nums[mid - 1]) {
        max = mid - 1;
      }
    } else {
      if (nums[mid] === nums[mid + 1]) {
        max = mid - 1;
      }
      if (nums[mid] === nums[mid - 1]) {
        min = mid + 1;
      }
    }
  }
}

我寫得真是醜…
MarsgoatTue, Feb 21, 2023














function singleNonDuplicate(nums) {
  let max = nums.length - 1;
  let min = 0;
  while (max > min) {
    const mid = ~~((max + min) / 2);
    if (nums[mid] === nums[mid ^ 1]) {
      min = mid + 1;
    } else {
      max = mid;
    }
  }

  return nums[min];
}

copilot教我寫的，順手分享一下，真的是簡約而不簡單。
MarsgoatTue, Feb 21, 2023

Reference

回到題目列表