LeetCode 540. 有序数组中的单一元素

川长思鸟来 2022-10-26 04:58 141阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[官方题解][Link 1]

//解法一：判断左右两边哪个长度为奇数，答案就在哪边
    class Solution {
        
        public int singleNonDuplicate(int[] nums) {
        
            int l = 0;
            int r = nums.length - 1;
            int L = 0;//左边长度
            int R = 0;//右边长度
            while(l < r){
        
                int mid = l + r >> 1;
                if(nums[mid] == nums[mid + 1]){
        
                    L = mid;//长度
                    if(L % 2 == 1)
                        r = mid - 1;
                    else
                        l = mid + 2;
                }else if(nums[mid] == nums[mid - 1]){
        
                    L = mid - 1;
                    if(L % 2 == 1)
                        r = mid - 2;
                    else
                        l = mid + 1;
                }else
                    return nums[mid];
            }
            return nums[r];
        }
    }

//解法二：对偶数索引进行二分
    class Solution {
        
        public int singleNonDuplicate(int[] nums) {
        
            int l = 0;
            int r = nums.length - 1;
            while(l < r){
        
                int mid = l + r >> 1;
                if(mid % 2 == 1)
                    mid--;
                if(nums[mid] == nums[mid + 1])
                    l = mid + 2;
                else
                    r = mid;
            }
            return nums[l];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/d7680006efda46a49ef0f3a865ea4297.png
[Link 1]: https://leetcode-cn.com/problems/single-element-in-a-sorted-array/solution/you-xu-shu-zu-zhong-de-dan-yi-yuan-su-by-leetcode/