二分查找---有序数组的 Single Element

2024-08-24 20:01:39

有序数组的 Single Element

540. Single Element in a Sorted Array (Medium)

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

Output: 2

题目描述：

一个有序数组只有一个数不出现两次，找出这个数。

思路分析：

要求在时间复杂度为O(lgn)内解出，因此不能遍历数组并进行异或操作进行求解，这么做的时间复杂度为O(n)。

令index为只出现一次数在数组中的下标，在index之后，数组中原来存在的成对状态被打破。如果m为偶数，并且m+1<index，那么nums[m]==nums[m+1]如果m+1>=index，那么nums[m]！=nums[m+1]。

从上面的规律知道，如果nums[m]==nums[m+1]，那么index存在于[m+2,h]，如果nums[m]！=nums[m+1]，那么index存在于[l,m]。因为h的赋值表达式为h=m，那么循环条件也就只能使用了l<h这种形式。

代码

public int singleNonDuplicate(int []nums){

    int l=0;

    int h=nums.length-1;

    while(l<h){

        int m=l+(h-l)/2;

        if(m%2==1)

            m--;   //保证l/h/m都在偶数位

        if(nums[m]==nums[m+1]){

            l=m+2;

        }else{

            h=m;

        }

    }

    return nums[l];

}

最新文章

热门文章