leetcode-剑指 Offer II 070. 排序数组中只出现一次的数字【java】

本文主要是介绍leetcode-剑指 Offer II 070. 排序数组中只出现一次的数字【java】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

剑指 Offer II 070. 排序数组中只出现一次的数字

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

示例 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 <= 105
0 <= nums[i] <= 105

进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？

代码1：异或

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int i,sum=0;
        for (i=0;i<nums.length;i++)
        sum=sum^nums[i];
        
        return sum;
    }
    
}

代码2：二分

public int singleNonDuplicate(int[] nums) {
        int left=0;
        int right=nums.length/2;
        while (left<=right)
        {
            int mid=(left+right)/2;
            int i=mid*2;
            if (i<nums.length-1&&nums[i]!=nums[i+1])
            {
                if (mid==0||nums[i-2]==nums[i-1])
                    return nums[i];
                
                right=mid-1;
            }
            else
                left=mid+1;
        }
        
        return nums[nums.length-1];
    }

这篇关于leetcode-剑指 Offer II 070. 排序数组中只出现一次的数字【java】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！