给定一个长度为 n 的有序数组,其中每个元素都出现两次,只有一个数仅出现一次。请你找出这个数。
你能在O(logn)的时间复杂度和O(1)的 空间复杂度下完成本题吗
数据范围:数组长度 ,数组中每个元素的值满足
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param v int整型一维数组 # @return int整型 # class Solution: """ 题目: https://www.nowcoder.com/practice/4c67fc80c37649ac906fee76ec82beb4?tpId=196&tqId=40508&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 算法: left, right = 0, len(v) - 1 当left < right时,二分查找res: mid = left + (right - left) / 2 如果v[mid] != v[left] and v[mid] != v[right]: return v[mid] 否则,如果v[mid] == v[mid - 1]: 若(mid + 1) % 2 == 0: # 解在区间[mid + 1, right] left = mid + 1 否则: right = mid - 2 否则: # v[mid] == v[mid + 1] 若mid % 2 == 0:# 解在区间[mid + 2, right] left = mid + 2 否则: right = mid - 1 复杂度: 时间复杂度:O(logN) 空间复杂度:O(1) """ def singleElement(self, v): # write code here left, right = 0, len(v) - 1 while left < right: mid = left + (right - left) / 2 if v[mid] != v[mid - 1] and v[mid] != v[mid + 1]: return v[mid] elif v[mid] == v[mid - 1]: if (mid + 1) % 2 == 0: # 解在区间[mid + 1, right] left = mid + 1 else: right = mid - 2 else: # v[mid] == v[mid + 1] if mid % 2 == 0: # 解在区间[mid + 2, right] left = mid + 2 else: right = mid - 1 return v[left] if __name__ == "__main__": sol = Solution() # nums = [1, 2, 2, 3, 3] # nums = [1, 1, 5, 5, 8, 8, 9, 10, 10] nums = [5, 5, 6, 6, 9, 10, 10, 11, 11, 13, 13, 14, 14] res = sol.singleElement(nums) print res