540. Single Element in a Sorted Array 排序数组中的单个元素

时间：2022-11-16 10:43:17

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.

给定一个排序数组，它只包含整数，每个元素出现两次，除了一个出现一次的元素。找到只出现一次的单个元素。

   
   
    

  1. class Solution(object):
    2. 
    
    
  2.  def singleNonDuplicate(self, nums):
    3. 
    
    
  3.  lo, hi = 0, len(nums) - 1
    4. 
    
    
  4.  while lo < hi:
    5. 
    
    
  5.  mid = int((lo + hi) / 2)
    6. 
    
    
  6.  if nums[mid] == nums[mid ^ 1]:
    7. 
    
    
  7.  lo = mid + 1
    8. 
    
    
  8.  else:
    9. 
    
    
  9.  hi = mid
    10. 
    
    
  10.  return nums[lo]
    11.

二分查找（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]
 
  
  
    

  1. class Solution(object):
    2. 
   
   
  2.  def singleNonDuplicate(self, nums):
    3. 
   
   
  3.  """
    4. 
   
   
  4.  :type nums: List[int]
    5. 
   
   
  5.  :rtype: int
    6. 
   
   
  6.  """
    7. 
   
   
  7.  lo, hi = 0, len(nums) - 1
    8. 
   
   
  8.  while lo < hi:
    9. 
   
   
  9.  mi = (lo + hi) >> 1
    10. 
   
   
  10.  if nums[mi] == nums[mi - 1]:
    11. 
   
   
  11.  if (mi - 1) & 1:
    12. 
   
   
  12.  hi = mi - 2
    13. 
   
   
  13.  else:
    14. 
   
   
  14.  lo = mi + 1
    15. 
   
   
  15.  elif nums[mi] == nums[mi + 1]:
    16. 
   
   
  16.  if (mi + 1) & 1:
    17. 
   
   
  17.  lo = mi + 2
    18. 
   
   
  18.  else:
    19. 
   
   
  19.  hi = mi - 1
    20. 
   
   
  20.  else:
    21. 
   
   
  21.  return nums[mi]
    22. 
   
   
  22.  return nums[lo]
    23.

出处：http://bookshadow.com/weblog/2017/03/11/leetcode-single-element-in-a-sorted-array/




来自为知笔记(Wiz)

标签：

相关文章