每日一题 540. 有序数组中的单一元素

简介: 每日一题 540. 有序数组中的单一元素

题:给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例:

输入: nums = [1,1,2,3,3,4,4,8,8]

输出: 2

解:看到题目 中O(log n) 时间复杂度,容易想到二分查找。难点是这题中不是查找某一个值,而是查找一个单独的数。条件 nums[mid] ?? target 要如何改变?

单独元素前面有n对元素,即2n个元素,所以单独元素的下标一定是偶数。对偶数下标二分搜索。

若它与num[mid+1]是一对,则说明前面的都是成对的,low= mid+2;否则说明前面有单独的,high = mid。

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1
        while low < high:
            mid = (low + high) // 2
            mid -= mid & 1
            #mid -= mid & 1 作用是让mid取偶数。&是按位与,奇数&1 = 1,偶数&1 =0。
 
            if nums[mid] == nums[mid + 1]:
                low = mid + 2
            else:
                high = mid
        return nums[low]
 

如果 while循环用 <= 条件,需要high 初始化为len(nums)-2,否则会数组越界。 搜索空间为[0,len(nums)-2],实际上mid最大取值len(nums)-2在区间内,所以有不会遗漏。

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 2
        while low <= high:
            mid = (low + high) // 2
            mid -= mid & 1
            if nums[mid] == nums[mid + 1]:
                low = mid + 2
            else:
                high = mid-2
        return nums[low]


相关文章
【LeetCode-每日一题】-378. 有序矩阵中第K小的元素
【LeetCode-每日一题】-378. 有序矩阵中第K小的元素
|
7月前
|
算法 测试技术 C#
【并集查找 图论 位运算】3108. 带权图里旅途的最小代价
【并集查找 图论 位运算】3108. 带权图里旅途的最小代价
|
7月前
|
算法
DAY-7 | 牛客-BM21 寻找旋转数组的最小元素:二分法分治思想真的很可靠
这是一个关于编程题目的摘要:题目是牛客网上的&quot;BM21 旋转数组的最小数字&quot;,要求找到旋转数组中的最小数字。题解介绍了使用二分查找算法来解决此问题,因为其时间复杂度优于暴力搜索的线性时间复杂度。二分查找的核心是通过比较中间元素与右端元素的大小,不断缩小搜索范围,最终找到最小值。代码示例展示了如何实现这个算法。总结中强调了二分查找适用于部分有序数组,并指出了解决这类问题的关键在于理解数组的二段单调性。
47 1
|
存储 搜索推荐 索引
基于元素小组的归并排序算法
基于元素小组的归并排序算法
86 0
|
7月前
|
存储 人工智能 Java
每日一题《剑指offer》数组篇之构建乘积数组
每日一题《剑指offer》数组篇之构建乘积数组
48 0
每日一题《剑指offer》数组篇之构建乘积数组
|
7月前
leetcode-540:有序数组中的单一元素
leetcode-540:有序数组中的单一元素
39 0
|
7月前
|
算法 vr&ar
1611F - ATM and Students详细题解(*1800,线段树维护前缀和;双指针算法(思维))
1611F - ATM and Students详细题解(*1800,线段树维护前缀和;双指针算法(思维))
52 0
|
7月前
|
算法 搜索推荐 Java
算法编程(四):合并两个有序数组
算法编程(四):合并两个有序数组
77 0
|
人工智能 算法 BI
算法每日一题(合并两个有序的数组)
算法每日一题(合并两个有序的数组)
121 0