leetcode540-有序数组中的单一元素

原题

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

示例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)空间复杂度中运行。

解法

思想

最优解法:二分查找达到O(log n)时间复杂度。

leetcode540-有序数组中的单一元素

保持数组个数为奇数(即永远只包含一个单一元素),每次取中间的元素,如果前面的元素与当前元素相等,又分两种情况:

  • 前面的元素个数为偶数个,则除去选中本身的这一对,前面的元素个数为奇数个,说明单一元素出现在该元素前面,可以把要查找的结束位置指向当前元素对之前,在图中下一步指向2。
  • 前面的元素个数为奇数个,则除去选中本身的这一对,前面的元素个数为偶数个,说明单一元素出现在该元素后面,可以把要查找的开始位置指向当前元素对之后,在图中下一步指向10。

如果当前元素和后面的元素相等情况也是类似的,可以逐一分析。

其他解法:暴力法,异或。

代码

二分查找:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        while(start<end){
            int mid = (start+end)/2;
            if(mid%2==0) {
                if(nums[mid-1]==nums[mid]) end = mid-2;
                else if(nums[mid+1] == nums[mid]) start = mid+2;
                else return nums[mid];
            }else{
                if(nums[mid-1]==nums[mid]) start = mid+1;
                else if(nums[mid+1] == nums[mid]) end = mid-1;
                else return nums[mid];
            }
        }
        return nums[start];
    }
}

暴力法:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i+=2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}

异或:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int cur=0;
        for (int i:nums) cur=cur^i;
        return cur;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode540-%e6%9c%89%e5%ba%8f%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e5%8d%95%e4%b8%80%e5%85%83%e7%b4%a0/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月24日
下一篇 2020年2月25日

相关推荐

  • leetcode260-只出现一次的数字III

    原题 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。 示例: 输入: [1,2,1,3,2,5] 输出: [3,5…

    算法 2020年4月28日
    0140
  • leetcode530-二叉搜索树的最小绝对差

    原题 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例: 输入:    1    &n…

    算法 2020年2月22日
    01320
  • leetcode1160-拼写单词

    原题 给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字…

    算法 2020年3月17日
    0130
  • leetcode63-不同路径II

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月22日
    0120
  • leetcode202-快乐数

    原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无…

    算法 2019年12月18日
    0110
  • leetcode264-丑数II

    原题 编写一个程序,找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, …

    算法 2020年2月10日
    0170
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    070
  • 海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源: 那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天…

    2020年2月28日
    01.3K0
  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    080
  • leetcode56-合并区间

    原题 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]…

    算法 2020年4月16日
    0160

发表回复

登录后才能评论