【每日一题】- Leetcode 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. Find this single element that appears only once.
Note:
- Your solution should run in O(log n) time and O(1) space.
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
Intuition:
1. O(logN), binary search
2. The subarray containing the single element must be odd-lengthed, and the subarray containing it must be even-lengthed.
3. Every time examine the middle element and its neighbor, taking out this pair and moving the lo/hi pointer according to the odd/even length of the subarray.
4. Solution:
class Solution { public int singleNonDuplicate(int[] nums) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int mid = lo + (hi - lo)/2; if (nums[mid] == nums[mid + 1]) { if ((hi -(mid + 2) + 1)%2 == 1) lo = mid + 2; else hi = mid - 1; } else if (nums[mid] == nums[mid - 1]) { if ((mid - 2 - lo + 1)%2 == 1) hi = mid - 2; else lo = mid + 1; } else return nums[mid]; } return nums[lo]; } }
Reference: https://leetcode.com/problems/single-element-in-a-sorted-array/