Geekerstar

【LeetCode】441.有序数组中的单一元素
题目给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。示例 1:输入: [1...
扫描右侧二维码阅读全文
19
2018/03

【LeetCode】441.有序数组中的单一元素

题目

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

示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

代码

public int singleNonDuplicate(int[] nums) {
    int l = 0, 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];
}

版权声明:本文(除特殊标注外)为原创文章,版权归 Geekerstar 所有。

本文链接:http://www.geekerstar.com/problem/584.html

除了有特殊标注文章外欢迎转载,但请务必标明出处,格式如上,谢谢合作。

本作品采用 知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议 进行许可。

最后修改:2018 年 03 月 19 日 06 : 48 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论