540. Single Element in a Sorted Array

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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^5
• 0 <= nums[i] <= 10^5

Code

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left + 1 < right) {
            int mid = (left + right) / 2;
            
            int num = nums[mid];
            
            if (num != nums[mid - 1] && num != nums[mid + 1]) return num;

            if (mid % 2 == 0) {
                if (num == nums[mid - 1]) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
                if (num == nums[mid - 1]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }

        // [1,2,2,3,3]
        if (left == 0) return nums[0];

        // [1,1,2]
        return nums[right];
    }
}