540.Single-Element-in-a-Sorted-Array

540. Single Element in a Sorted Array

题目地址

https://leetcode.com/problems/single-element-in-a-sorted-array/

题目描述

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

Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10

代码

Approach 0: use XOR

O(n)

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}

Approach 1: Binary Search

O(logN)

class Solution {
  public int singleNonDuplicate(int[] nums) {
        int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      // 0: 前一个数组为奇数，1：前一个数组为偶数
      boolean halvesAreEven = (hi - mid) % 2 == 0;
      if (nums[mid] == nums[mid + 1]) {
        if (halvesAreEven) { 
// Case 1: Mid’s partner is to the right, and the halves were originally even
          lo = mid + 2; 
        } else {
// Case 2: Mid’s partner is to the right, and the halves were originally odd
          hi = mid - 1;    
        }
      } else if (nums[mid - 1] == nums[mid]) {
        if (halvesAreEven) {
// Case 3: Mid’s partner is to the left, and the halves were originally even
          hi = mid - 2; 
        } else {
// Case 4: Mid’s partner is to the left, and the halves were originally odd
          lo = mid + 1;
        }
      } else {
        return nums[mid];
      }
    }

    return nums[lo];
  }
}

Approach #3 Binary Search on Evens indexes Only

O(logN)

class Soluton {
  public int singleNonDuplicate(int[] nums) {
    int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (mid % 2 == 1) mid--;
      if (nums[mid] == nums[mid + 1]) {
        lo = mid + 2;
      } else {
        hi = mid;
      }
    }
    return nums[lo];
  }
}