LeetCode #540 有序数组中的单一元素

本贴最后更新于 1323 天前,其中的信息可能已经时异事殊

540.png

Problem Description

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

note

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

e.g.

  • 示例 1:

    输入: [1,1,2,3,3,4,4,8,8]
    输出: 2
    
  • 示例 2:

    输入: [3,3,7,7,10,11,11]
    输出: 10
    

Solution

题目很简单,但是题干中重点强调了 O(logn)的时间复杂度和 O(1)空间复杂度,所以一切会伴随输入数组大小变化的额外空间和遍历也不行哦,即使是用双指针优化到 O(logn/4)也是不满足的。一眼看到 O(logn)的时间复杂度就想到了题目的本意应该是让我们利用二分法来解。

因为是有序数组,并且每个元素都是出现两次,除了唯一的一个元素。所以相同的元素一定是连续的并且长度为奇数,所以我们可以每次取中间的元素,和左右两边比较(注意边界),找出相邻元素相同的情况,将整个数组分隔开,左边的子串和右边子串一定有一个是奇数长度(该数组一定有个唯一元素),单个元素就一定藏在这个子串里。

540bisection.jpeg

public static int singleNonDuplicate(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (mid - 1 >= 0 && nums[mid] == nums[mid - 1]) {
            // 奇数在左边
            if (((mid - 1) & 1) == 1) {
                right = mid - 2;
            } else {
                left = mid + 1;
            }

        } else if (mid + 1 < nums.length && nums[mid] == nums[mid + 1]) {
            // 奇数在左边
            if ((mid & 1) == 1) {
                right = mid - 1;
            } else {
                left = mid + 2;
            }
        } else {
            return nums[mid];
        }
        System.out.println("left = " + left);
        System.out.println("right = " + right);

    }
    return 0;
}
  • 二分查找
    4 引用 • 21 回帖
  • 算法
    388 引用 • 254 回帖 • 22 关注
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖
1 操作
matthewhan 在 2020-08-14 10:42:40 更新了该帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...