hot100——二分查找

4.寻找两个正序数组的中位数解题思路首先题目中已经说明是正序那么nums1以及nums2中都是从小到大进行排列的又因为题目中要求时间复杂度为O(log(mn))一般看到这种时间复杂度是O(log……)形式的基本上就要想到二分法。那么我们开始划分这两个数组首先我们要确保nums1的数组长度nums2数组的长度因为我们之后是在nums1数组上遍历这样的话在较短的数组内部进行遍历时间复杂度比较小。对于数组nums1nums2,取中间i, j一般中位数的话左边和右边是相同的但是如果数组长度是奇数的话那么左边的长度比右边的要大1。对于nums1nums2取中间ij;那么左半部分就是nums1[0,……i-1] nums2[0,……,j-1]右半部分就是nums1[i,……m] nums2[j,……, n]对于这些部分需要满足左边的最大值小于等于右边的最小值也即nums1[i-1] num2[j]nums2[j-1] nums1[i]如果nums1[i-1] nums2[j]说明nums1左半部分的最大值竟然大于nums2右半部分的最小值说明i值大了应该把nums1[i-1]往左移nums2[j]往右移这样确保nums1[i-1]变小nums2[j]变大同理如果nums2[j-1] nums1[i]说明nums2左半部分的最大值竟然大于nums1右半部分的最小值说明i值小了应该把nums2[j-1]往左移nums1[i]往右移这样确保nums2[j-1]变小nums1[i]变大。代码pythonclass Solution(object): def findMedianSortedArrays(self, nums1, nums2): :type nums1: List[int] :type nums2: List[int] :rtype: float m , n len(nums1), len(nums2) if m n : return self.findMedianSortedArrays(nums2, nums1) left, half, right 0 , (mn1)//2, m while left right: i (left right) // 2 j half - i left1 nums1[i-1] if i 0 else float(-inf) right1 nums1[i] if i m else float(inf) left2 nums2[j-1] if j 0 else float(-inf) right2 nums2[j] if j n else float(inf) if left1 right2 and left2 right1: if (mn) % 2 1: return max(left1, left2) else: return (max(left1, left2) min(right1, right2)) / 2.0 elif left1 right2: right i - 1 else: left i 1 return 0.0Cclass Solution { public: double findMedianSortedArrays(vectorint nums1, vectorint nums2) { int m nums1.size(); int n nums2.size(); // 让二分在数组长度小的数组内进行降低时间复杂度 if(m n) return findMedianSortedArrays(nums2, nums1); int total m n; // 取一半的数作为左边一般左边数量右边当总数为奇数的时候左边比右边多一个中位数 int half (total1)/2; int left 0; int right m; while(left right) { int i (left right) / 2; int j half - i; // 取nums1一半的数作为左半边, nums2一半的数作为左半边 // 取nums1一半的数作为右半边nums2一半的数作为右半边 int left1 (i 0? nums1[i-1] : INT_MIN); int right1 (i m? nums1[i] : INT_MAX); int left2 (j 0? nums2[j-1] : INT_MIN); int right2 (j n? nums2[j] : INT_MAX); if(left1 right2 left2 right1) { if(total%21) return max(left1, left2); else return (max(left1, left2)min(right1,right2))/2.0; } else if(left1 right2) // nums1左边的最大值竟然大于nums2右边的最小值不合理说明i大了应该减小 right i - 1; else // nums2左边的最大值竟然大于nums1右边的最小值不合理说明i小了应该增大 left i 1; } return 0.0; } };33.搜索旋转排序数组解题思路首先我们从题目中已知整个数组在未旋转之前是升序排序的经旋转后不是升序的了题目中要求时间复杂度是O(logn)一看到整个logn这就让我们想起了二分法。我们知道在旋转后数组中旋转后的部分和没旋转的部分都是升序排列的比如[0,1,2,4,5,6,7]下标3上向左旋转后可能变为[4,5,6,7,0,1,2]。旋转后的部分[4, 5, 6, 7] 以及 [0, 1, 2]都是升序排列的。我们取left0, right len(nums)-1,mid (leftright)/2把整个数组分成2部分一部分是[left, mid)一部分是(mid, right]。返回条件是nums[mid] target, return mid随后判断这俩部分是否是升序。如果nums[left] nums[mid]则说明左半部分是有序的之后再判断target是否是在整个左半部分nums[left]target target nums[mid]如果条件成立则说明target在左半部分那么right mid - 1;反之则说明target在右半部分left mid 1反之上述条件不成立则说明右半部分是有序的之后再判断target是否是在右半部分nums[mid]target target nums[right]如果条件成立则说明target在右半部分那么left mid 1;反之则说明target在左半部分right mid - 1;反之则说明该target不存在。代码pythonclass Solution(object): def search(self, nums, target): :type nums: List[int] :type target: int :rtype: int left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid # 左半部分升序 if nums[left] nums[mid]: # target在左半边 if nums[left] target and target nums[mid]: right mid - 1 # target在右半边 else: left mid 1 # 右半部分升序 else: # target在右半边 if nums[mid] target and target nums[right]: left mid 1 # target在左半边 else: right mid - 1 return -1Cclass Solution { public: int search(vectorint nums, int target) { int left 0; int right nums.size() - 1; while(left right) { // mid取left 和 right的中间数 int mid (right left) / 2; // 当nums[mid] target时返回mid if(nums[mid] target) return mid; // 二分法分为2部分判断左右2部分是否为有序 // 左半部分是升序 if(nums[left] nums[mid]) { // target是在[left, mid)这个区间内 if(nums[left] target target nums[mid]) right mid - 1; // target在(mid, right]这个区间内 else left mid 1; } // 右半部分升序 else { // target是在(mid, right]这个区间内 if(nums[mid] target target nums[right]) left mid 1; // target在[left, mid)这个区间内 else right mid - 1; } } return -1; } };34.在排序数组中查找元素的第一个和最后一个位置解题思路首先题目中说了目前我们的数组是非递减顺序排列的数组其实要求时间复杂度是O(logn)可知该题应该用到二分法。因为target在数组中可能不止一个与target相等的数值题目中也要求了返回给定目标值在数组当中的开始位置以及结束位置所以我们需要找到数组最左边以及最右边和target相等的数值的下标然后返回对应的下标列表。二分法查找左边界当我们找到nums[mid]target时不立即返回而是向左继续查找等于target的数返回对应的下标。初始化left0, rightlen(nums)-1. return -1;当leftright时mid (leftright) // 2;判断nums[mid]target?条件成立则说明mid左侧确实是可能有和target相等的数存在那么right mid - 1条件不成立则说明mid右侧可能存在和target相等的数那么缩小左边界left mid 1循环结束后left就是最后一个target的值比较nums[left] target来判断是否返回left。二分法查找右边界当我们找到nums[mid]target时不立即返回而是向右继续查找等于target的数返回对应的下标。初始化left0, rightlen(nums)-1. return -1;当leftright时mid (leftright) // 2;判断nums[mid]target?条件成立则说明mid右侧确实是可能有和target相等的数存在那么left mid 1条件不成立则说明mid左侧可能存在和target相等的数那么缩小右边界right mid - 1循环结束后right就是最后一个target的值比较nums[right] target来判断是否返回right。代码pythonclass Solution(object): def searchRange(self, nums, target): :type nums: List[int] :type target: int :rtype: List[int] left self.findleft(nums, target) if left -1: return [-1, -1] right self.findright(nums, target) return [left, right] # 往target左边找找到最左边的target下标 def findleft(self, nums, target): :type nums: List[int] :type target: int :rtype: List[int] left, right 0, len(nums) -1 while left right: mid (left right) // 2 # 左边还可能有target if nums[mid] target: right mid - 1 # 收缩左边界 else: left mid 1 if (left len(nums)) and (nums[left] target): return left return -1 # 往target右边找找到最右边的target下标 def findright(self, nums, target): :type nums: List[int] :type target: int :rtype: List[int] left, right 0, len(nums) -1 while left right: mid (left right) // 2 # 右边还可能有target if nums[mid] target: left mid 1 # 收缩右边界 else: right mid - 1 if (right 0) and (nums[right] target): return right return -1Cclass Solution { public: // 找到最左边等于target的下标 int findleft(vectorint nums, int target) { int left 0; int right nums.size() - 1; while(left right) { int mid (left right) / 2; if(nums[mid] target) // 说明左边可能还有和target相等的数 right mid - 1; else //缩小左边界 left mid 1; } if(left nums.size() nums[left] target) return left; return -1; } // 找到最右边等于target的下标 int findright(vectorint nums, int target) { int left 0; int right nums.size() - 1; while(left right) { int mid (left right) / 2; if(nums[mid] target) // 说明右边可能还有和target相等的数 left mid 1; else //缩小右边界 right mid - 1; } if(right 0 nums[right] target) return right; return -1; } vectorint searchRange(vectorint nums, int target) { int left findleft(nums, target); if(left -1) return {-1, -1}; int right findright(nums, target); return {left, right}; } };240.搜索二维矩阵II解题思路首先从题目中我们可以得知矩阵是每一行从左到右升序排列每一列的元素从上到下升序排列。因此我们取矩阵的右上角元素和target进行比对如果右上角元素和target相同则返回True如果右上角元素大于target那么当前列的元素都是大于target的那么只能往左靠因此j - 1如果右上角元素小于target那么当前行的元素都是小于target的那么只能往下靠因此i 1如果这样遍历了整个矩阵都没找到的话就返回false。因此整个时间复杂度是O(mn)。代码pythonclass Solution(object): def searchMatrix(self, matrix, target): :type matrix: List[List[int]] :type target: int :rtype: bool if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) i, j 0, n-1 while i m and j 0: if matrix[i][j] target: return True elif matrix[i][j] target: j - 1 else: i 1 return FalseCclass Solution { public: bool searchMatrix(vectorvectorint matrix, int target) { int m matrix.size(); int n matrix[0].size(); int i 0; int j n - 1; // 取矩阵的右上角元素开始比对 while(i m j 0) { if(matrix[i][j] target) return true; else if(matrix[i][j] target) j - 1; else i 1; } return false; } };