[LeetCode]Single Element in a Sorted Array

题目描述:

LeetCode 540. Single Element in a Sorted Array

Given a sorted array consisting of only integers where every element appears twice except for one element which appears 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)空间约束。

解题思路:

二分查找(Binary Search)

从数组递增有序和O(log n)时间复杂度推断,题目可以采用二分查找求解。

初始令左、右指针lo, hi分别指向0, len(nums) - 1

当lo < hi时执行循环:

令mi = (lo + hi) / 2

若nums[mi] == nums[mi - 1]:

数组可以分为[lo, mi - 2], [mi + 1, hi]两部分,目标元素位于长度为奇数的子数组中。

同理,若nums[mi] == nums[mi + 1]:

数组可以分为[lo, mi - 1], [mi + 2, hi]两部分,目标元素位于长度为奇数的子数组中。

若nums[mi]与nums[mi - 1], nums[mi + 1]均不相等,则返回nums[mi]

Python代码:

class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mi = (lo + hi) >> 1
            if nums[mi] == nums[mi - 1]:
                if (mi - 1) & 1:
                    hi = mi - 2
                else:
                    lo = mi + 1
            elif nums[mi] == nums[mi + 1]:
                if (mi + 1) & 1:
                    lo = mi + 2
                else:
                    hi = mi - 1
            else:
                return nums[mi]
        return nums[lo]

 

本文链接:http://bookshadow.com/weblog/2017/03/11/leetcode-single-element-in-a-sorted-array/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. 书影网友 书影网友 发布于 2017年4月11日 09:52 #

    if (mi + 1) &amp; 1: 这个不懂, mi+1 永远都大于1呀, 所以这个条件永远成立

  2. 书影网友 书影网友 发布于 2017年4月12日 10:55 #

    这里有个位与运算(&amp;),这个条件不会永远成立的

张贴您的评论