专栏首页眯眯眼猫头鹰的小树杈leetcode540. Single Element in a Sorted Array

leetcode540. Single Element in a Sorted Array

题目要求

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Example 1:

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

Example 2:

Input: [3,3,7,7,10,11,11] Output: 10

Note:Your solution should run in O(log n) time and O(1) space.

现有一个有序的递增的整数数组,其中除了一个数字之外,每个数字都出现了两次。要求用O(log n)的时间复杂度和O(1)的空间复杂度找出只出现一次的数字。

思路一:位运算

已知 a ^ a = 0,利用这个结论,可以对所有的数字执行异或操作,最终异或的结果就是只出现一次的数字。

public int singleNonDuplicate(int[] nums) {  
    int result = 0;  
    for (int num : nums) {  
        result ^= num;  
    }  
    return result;  
}

思路二:二分法

O(log n)的时间复杂度通常都和二分法有关,而这里的二分法的思考点在于如何寻找中间位置,以及用什么判断逻辑来决定是继续递归处理左子数字还是右子数组。

一旦找到合适的中间位置,我们就应该可以判断出来单个数字究竟是出现在左子数字还是右子数字。那么我们的目标就应该是找到中间的重复数对的第一个数字。假如我们默认左子数组中不存在单个数字,则说明中间数对应该是位于一个偶数下标上,如下:

0 1 2 3 4
1 1 3 3 5
    ^

但是假如单个数字在左子数组,则我们找到的中间位置偶数下标上的数字就不是重复数对的第一个下标

0 1 2 3 4
1 2 2 3 3
    ^

因此找到中间位置的偶数下标上的值,并且和后面的数字进行比较,就知道单个数字究竟在左边还是在右边。

public int singleNonDuplicate2(int[] nums) {  
    int start = 0, end = nums.length - 1;  
    while (start < end) {  
        int mid = (start + end) / 2;  
        //假设左半边子数组均为重复数字,则默认的中间数对的第一个数字的下标一定为偶数  
 //找到中间数对第一个数字的下标  
    if (mid % 2 == 0) {mid -= 1;}  
        //中间数对为重复数字,说明单个数字在右半边  
    if (nums[mid] == nums[mid + 1]) {  
            start = mid + 2;  
        } else {  
            end = mid - 1;  
        }  
    }  
    return start;  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode363. Max Sum of Rectangle No Larger Than K

    现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标...

    眯眯眼的猫头鹰
  • leetcode310. Minimum Height Trees

    在无向图的生成树中,我们可以指定任何一个节点为这棵树的根节点。现在要求在这样一棵生成树中,找到生成树的高度最低的所有根节点。

    眯眯眼的猫头鹰
  • 547. Friend Circles

    There are N students in a class. Some of them are friends, while some are not. T...

    眯眯眼的猫头鹰
  • LeetCode 260. Single Number III

    题解:我们先把整个数组连着异或一遍,得到的结果是那两个不同数字的异或结果,其结果必然大于等于1 我们把结果中第一个为1的位,作为判断条件。如果数组中相应位为1...

    ShenduCC
  • 【map超时】【set超时】1-5 两个有序序列的中位数 (25 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • Dimple在左耳听风ARTS打卡(第一期)

    参加了左耳听风的ARTS打卡,坚持一个月,对自己会有什么情况呢,我不知道,但我会照着这个目标坚持下去,坚持100天。一个习惯养成是21天,那如果坚持100天,效...

    程序员小跃
  • LeetCode 45 Jump Game II

    这道题目乍一看,我以为是动态规划。可是LeetCode 从来不给数据范围。,又是hard难度的题目,所以我猜测数组长度至少10万吧。

    ShenduCC
  • 全排列的两种实现方式(java)-poj2718

    上述方法虽然能够实现全排列,但是方法的复杂度还是很高。指数级别增长。因为要遍历很多没用的情况。所以当数据较大并不能高速处理。所以换一种思路处理。 设[a,b,c...

    bigsai
  • hdu 1598 find the most comfortable road(枚举+卡鲁斯卡尔最小生成树)

    find the most comfortable road Time Limit: 1000/1000 MS (Java/Others)    Memory ...

    Gxjun
  • 【2020HBU天梯赛训练】7-30 树的遍历

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    韩旭051

扫码关注云+社区

领取腾讯云代金券