60. 搜索插入位置给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(log n)的算法。class Solution(object): def searchInsert(self, nums, target): left0 rightlen(nums)-1 result-1 while(leftright): midleft(right-left)//2 if nums[mid]target: leftmid1 elif nums[mid]target: rightmid-1 else: resultmid rightmid-1 return left if result-1 else result61. 搜索二维矩阵给你一个满足下述两条属性的m x n整数矩阵每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数target如果target在矩阵中返回true否则返回false。class Solution(object): def searchMatrix(self, matrix, target): m,nlen(matrix),len(matrix[0]) i,j0,n-1 while im and j0: if matrix[i][j]target: i1 elif matrix[i][j]target: j-1 else: return True return False62. 在排序数组中查找元素的第一个和最后一个位置给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。class Solution(object): def searchRange(self, nums, target): left0 rightlen(nums)-1 result_left-1 result_right-1 while(leftright): midleft(right-left)//2 if nums[mid]target: rightmid-1 elif nums[mid]target: leftmid1 else: result_leftmid rightmid-1 left0 rightlen(nums)-1 while(leftright): midleft(right-left)//2 if nums[mid]target: rightmid-1 elif nums[mid]target: leftmid1 else: result_rightmid leftmid1 return [result_left,result_right]63. 搜索旋转排序数组整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了向左旋转使数组变为[nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标从 0 开始计数。例如[0,1,2,4,5,6,7]下标3上向左旋转后可能变为[4,5,6,7,0,1,2]。给你旋转后的数组nums和一个整数target如果nums中存在这个目标值target则返回它的下标否则返回-1。你必须设计一个时间复杂度为O(log n)的算法解决此问题。class Solution(object): def search(self, nums, target): if not nums: return -1 left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -164. 寻找旋转排序数组中的最小值已知一个长度为n的数组预先按照升序排列经由1到n次旋转后得到输入数组。例如原数组nums [0,1,2,4,5,6,7]在变化后可能得到若旋转4次则可以得到[4,5,6,7,0,1,2]若旋转7次则可以得到[0,1,2,4,5,6,7]注意数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值互不相同的数组nums它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。你必须设计一个时间复杂度为O(log n)的算法解决此问题。class Solution(object): def findMin(self, nums): left,right0,len(nums)-1 mfloat(inf) while leftright: midleft(right-left)//2 if nums[left]nums[mid]: if nums[left]m: mnums[left] leftmid1 else: if nums[mid]m: mnums[mid] rightmid-1 return m65. 寻找两个正序数组的中位数给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log (mn))。class Solution(object): def getE(self,nums1,nums2,k): if not nums1: return nums2[k-1] if not nums2: return nums1[k-1] if k1: return min(nums1[0],nums2[0]) imin(len(nums1),k//2)-1 jmin(len(nums2),k//2)-1 if nums1[i]nums2[j]: return self.getE(nums1[i1:],nums2,k-i-1) else: return self.getE(nums1,nums2[j1:],k-j-1) def findMedianSortedArrays(self, nums1, nums2): klen(nums1)len(nums2) if k%20: return (self.getE(nums1,nums2,k//2)self.getE(nums1,nums2,k//21))/2.0 else: return self.getE(nums1,nums2,k//21)
