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

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

提示:

• 1 <= nums.length <= 10e5
• 0 <= nums[i] <= 10e5

 分析：根据题目要求，首先想到二分。对于当前的位置mid，如果它不是唯一出现的数，那么它的左边或者右边去掉和它相等的数字之后，一定有一边只有奇数个数字，此时进入这一边再次二分。边界条件为数组大小为1，或者mid仅出现过一次。

int getans(int *arr,int n,int l,int r)
{
    if(r==l)return arr[l];
    int mid=(l+r)/2;
    if(mid-1>=0&&mid+1<n)
    {
        int temp=arr[mid];
        if(arr[mid-1]==temp||arr[mid+1]==temp)
        {
            if(arr[mid-1]==temp)
            {
                if((mid+1-2)%2==1)return getans(arr,n,l,mid-2);
                else return getans(arr,n,mid+1,r);
            }
            else
            {
                if((mid)%2==1)return getans(arr,n,l,mid-1);
                else return getans(arr,n,mid+2,r);
            }
            
        }
    }
    return arr[mid];
}

int singleNonDuplicate(int* nums, int numsSize) {
    return getans(nums,numsSize,0,numsSize-1);
}

原文地址：https://blog.csdn.net/2401_88085478/article/details/143688433

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！