Java教程

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】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!