您在工信部门备案网站获取的icp备案号,网站建设与设计教程视频,网站cdn自己做,地产集团网站建设【LeetCode HOT 100】详细题解之二分查找篇 35 搜索插入位置思路代码(左闭右闭)代码(左闭右开) 74 搜索二维矩阵思路代码(左闭右闭) 34 在排序数组中查找元素的第一个和最后一个位置思路代码 33 搜索旋转排序数组思路代码 153 寻找旋转排序数组中的最小值思路代码 4 寻找两个正… 【LeetCode HOT 100】详细题解之二分查找篇 35 搜索插入位置思路代码(左闭右闭)代码(左闭右开) 74 搜索二维矩阵思路代码(左闭右闭) 34 在排序数组中查找元素的第一个和最后一个位置思路代码 33 搜索旋转排序数组思路代码 153 寻找旋转排序数组中的最小值思路代码 4 寻找两个正序数组的中位数思路代码 35 搜索插入位置
35. 搜索插入位置
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5
输出: 2示例 2:
输入: nums [1,3,5,6], target 2
输出: 1示例 3:
输入: nums [1,3,5,6], target 7
输出: 4提示:
1 nums.length 104-104 nums[i] 104nums 为 无重复元素 的 升序 排列数组-104 target 104
思路
一般使用二分查找算法需要满足以下两个条件
用于查找的内容有序查找的数量只能是一个而不是多个
举个例子在一个有序且无重复元素的数组中例如nums[1,3,4,8,15,16,18,28]中查找元素16这样就可以使用二分查找。 二分查找中目标元素的查找区间定义十分重要。我们要确定查找的范围。主要有以下两种方式 [left,right] 左闭右闭 此时while循环为while(leftright) [left,right) 左闭右开此时while循环为while(leftright)这两种方式的实现会在while循环的判断以及对right的更新上存在一定的区别。在下面会进行详细说明。 用二分查找查找区间为[left,right] 左闭右闭的操作查找步骤如下
nums[1,3,4,8,15,16,18,28]
下标 0,1,2,3,4, 5 , 6, 7 l 0, r nums.length -1 7 mid (lr)/2 3 比较nums[mid] 8和target 16 的大小 nums[mid]target 说明[mid,right]区间内的所有元素都大于target,此时要去[left,mid-1]区间中查找更新右边界right right mid -1; nums[mid]target 816,说明要在[mid1,right]中找 说明[left,mid]区间内的所有元素都小于target,此时要去[mid1,right]区间中查找,更新左边界left left mid 1 nums[mid]target ,直接return mid
不断循环123直到找到为止若循环完都没有return说明查找元素在数组中不存在
代码(左闭右闭)
class Solution {public int searchInsert(int[] nums, int target) {/**二分查找查找区间写为[left,right]*/int l 0,r nums.length-1;while(l r){int mid l (r-l)/2;if(nums[mid]target){ //注意这里是将r 更新为mid - 1r mid-1;}else if(nums[mid]target){l mid 1;}else if(nums[mid]target){return mid;}}return l;}
}代码(左闭右开)
class Solution {public int searchInsert(int[] nums, int target) {/**二分查找查找区间写为[left,right]*/int l 0,r nums.length; //这里r是nums.length,因为查找范围不包括nums[r]while(l r){ //这里是lr,因为查找范围为[l,r)int mid l (r-l)/2;if(nums[mid]target){r mid; //这里r mid,因为查找范围不包括r}else if(nums[mid]target){l mid 1;}else if(nums[mid]target){return mid;}}return l;}
}74 搜索二维矩阵
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target 如果 target 在矩阵中返回 true 否则返回 false 。
示例 1 输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3
输出true示例 2 输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 13
输出false思路
挺简单的遍历每一行获取每一行的第一个元素和最后一个元素判断target是否在该行中。若在该行中则使用二分查找若不在则继续遍历下一行。
代码(左闭右闭)
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m matrix.length;int n matrix[0].length;for(int i 0;im;i){if(targetmatrix[i][0] target matrix[i][n-1]){int l 0,r n-1;while(lr){int mid l (r-l)/2;if(matrix[i][mid]target){r mid -1;}else if(matrix[i][mid]target){l mid 1;}else if(matrix[i][mid]target){return true;}}}}return false;}
}34 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [5,7,7,8,8,10], target 8
输出[3,4]示例 2
输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]示例 3
输入nums [], target 0
输出[-1,-1]提示
0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109
思路
二分查找的变体。
本题中会存在重复的元素所以需要用二分查找来找到某个元素在数组中第一次出现的位置。将二分查找算法写成函数lowerBound该函数会找到target第一次出现的位置。调用两次该方法第一次查找target第二次查找target1这样就能成功返回目标在数组中的开始位置和结束位置。
我们需要考虑边界情况。如果数组为空或者所有数都target,那么会返回nums.length因此lowerBound返回值为nums.length时直接返回-1-1此外还需要判断lowerBound返回的下标在数组中对应的值是否等于target。
lowerBound如何实现呢和二分查找的差别在于更新右边界不管nums[mid] target还是nums[mid]target , 都会一直往左找直到找到该元素第一次出现的位置。
if(numd[mid]target){ l mid 1; }else{ r mid - 1; //这里不管nums[mid] target还是nums[mid]target , 都会一直往左找直到找到第一个 }
代码
class Solution {public int[] searchRange(int[] nums, int target) {int start lowerBound(nums,target);if(start nums.length || nums[start] !target){return new int[]{-1,-1};}int end lowerBound(nums,target1)-1;return new int[]{start,end};}/**lowerBound返回 [最小的]满足nums[i]target的i 如何实现呢也可以理解为找到target第一次出现的位置。如果数组为空或者所有数都target,那么会返回nums.lengthif(numd[mid]target){l mid 1;}else{r mid - 1; //这里不管nums[mid] target还是nums[mid]target , 都会一直往左找直到找到第一个}*/public int lowerBound(int[] nums,int target){int l 0,r nums.length-1;while(lr){int mid l (r-l)/2;if(nums[mid]target){r mid - 1;}else if(nums[mid]target){l mid 1;}else if(nums[mid]target){r mid - 1;}}return l;}
}33 搜索旋转排序数组
33. 搜索旋转排序数组
整数数组 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) 的算法解决此问题。
示例 1
输入nums [4,5,6,7,0,1,2], target 0
输出4示例 2
输入nums [4,5,6,7,0,1,2], target 3
输出-1示例 3
输入nums [1], target 0
输出-1提示
1 nums.length 5000-104 nums[i] 104nums 中的每个值都 独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转-104 target 104
思路
题目分析
本题是在一个可能经过旋转的有序数组中查找给定目标值的问题。由于数组经过旋转所以它被分为了两个部分一部分是有序的另一部分是无序的。我们需要利用这个特点来进行高效的查找。 二分查找每次查找一定能有一部分是有序的一部分是无序的 判断target在哪部分若在有序的部分则直接二分查找若在无序的部分就继续切割为有序和无序 解题思路
初始化指针 首先定义两个指针 l 和 r分别指向数组的首尾位置表示当前搜索的区间。 循环查找 进入一个循环只要 l 不超过 r就继续查找。在每次循环中计算当前区间的中间位置 mid即 mid l (r - l)/2。 情况判断 如果 nums[mid] 等于目标值 target说明找到了目标直接返回 mid。如果 nums[mid] 不等于目标值需要判断当前的中间位置处于哪个区间有序区间还是无序区间。如果nums[l] nums[mid]说明左边[l, mid]是有序区间 如果目标值 target 在这个有序区间内即 nums[l] target nums[mid] target那么更新 r 为 mid - 1继续在有序区间中查找。如果目标值不在这个有序区间内说明在无序区间中此时更新 l 为 mid 1。 如果nums[mid] nums[r]说明右边[mid, r]是有序区间 如果目标值 target 在这个有序区间内即 nums[mid] target nums[r] target那么更新 l 为 mid 1继续在有序区间中查找。如果目标值不在这个有序区间内说明在无序区间中此时更新 r 为 mid - 1。 返回结果 如果循环结束后还没有找到目标值说明目标值不在数组中返回 -1。
三、算法复杂度分析
时间复杂度 由于每次循环都将搜索区间缩小一半所以时间复杂度为O(logn) 其中 n 是数组的长度。 空间复杂度 算法只使用了几个额外的变量不随输入规模增长而增长所以空间复杂度为O(1) 。
代码
class Solution {public int search(int[] nums, int target) {/**二分查找每次查找一定能有一部分是有序的一部分是无序的判断target在哪部分若在有序的部分则直接二分查找若在无序的部分就继续切割为有序和无序*/int l 0,r nums.length-1;while(lr){int mid l (r-l)/2;//1.如果当前数等于target直接返回if(nums[mid]target){return mid;}else if(nums[l]nums[mid]){//2.左边[l,mid]是顺序区间//2.1判断当前元素是否在顺序区间中,若在顺序区间中更新r为mid-1继续在顺序区间中查找if(nums[l] target nums[mid]target){r mid - 1;}else{ //不在顺序区间中在无序区间中l mid 1;}}else if(nums[mid]nums[r]){//3.右边[mid,r]是顺序区间//3.1 判断当前元素是否在顺序区间中//3.2 若在顺序区间中更新l 为mid 1,继续在顺序区间[l,r]中查找if(nums[mid]target nums[r]target){l mid 1;}else{r mid - 1; //在无需区间中查找}}}return -1;}
}153 寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值
已知一个长度为 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) 的算法解决此问题。
示例 1
输入nums [3,4,5,1,2]
输出1
解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。示例 2
输入nums [4,5,6,7,0,1,2]
输出0
解释原数组为 [0,1,2,4,5,6,7] 旋转 3 次得到输入数组。示例 3
输入nums [11,13,15,17]
输出11
解释原数组为 [11,13,15,17] 旋转 4 次得到输入数组。提示
n nums.length1 n 5000-5000 nums[i] 5000nums 中的所有整数 互不相同nums 原来是一个升序排序的数组并进行了 1 至 n 次旋转
思路
实现思路
利用二分查找的思想通过比较中间元素和数组末尾元素的大小关系来确定最小值所在的区间不断缩小区间范围直到找到最小值。由于数组经过旋转后被分为了两个部分一部分是原升序数组的某个子区间另一部分是旋转后的子区间最小值就在这两个区间的交界处。通过比较中间元素和末尾元素可以确定当前中间元素处于哪个子区间从而缩小查找范围。
具体实现步骤
初始化指针 定义两个指针 l 和 r分别指向数组的首和尾位置表示当前搜索的区间范围。初始时l 0r nums.length - 1。 进入循环 进入一个循环只要 l 小于等于 r就继续查找。 计算中间位置 在每次循环中计算当前区间的中间位置 mid即 mid l (r - l)/2。 情况判断与区间调整 如果nums[mid] nums[n - 1] 说明 [mid, r] 为翻转后的递增区间此时最小值一定在 [l, mid - 1] 中所以将 r 更新为 mid - 1。 如果nums[mid] nums[n - 1] 说明 [l, mid] 为未翻转的递增区间那最小值一定在 [mid 1, r] 中所以将 l 更新为 mid 1。 如果nums[mid] nums[n - 1] 说明无法确定最小值在哪个区间但因为最终要返回 l所以将 r 更新为 mid - 1缩小搜索范围。 返回结果 循环结束后l 指向的位置就是数组中的最小值返回 nums[l]。
算法复杂度分析
时间复杂度 由于每次循环都将搜索区间缩小一半所以时间复杂度为 O(logn)其中 n 是数组的长度。 空间复杂度 算法只使用了几个额外的变量不随输入规模增长而增长所以空间复杂度为 O(1)。
代码
class Solution {public int findMin(int[] nums) {/**[4,5,6,7,0,1,2]使用nums[mid]和nums[n-1]比不停的拿中间的数和最后一个数比较缩小区间一共有三种情况nums[mid]nums[n-1] : 说明[mid,r]为翻转后的递增区间,此时最小值一定在[l,mid-1]中nums[mid]nums[n-1]: 说明[l,mid]为未翻转的递增区间那最小值一定在[mid1,r]中nums[mid]nums[n-1]:说明最小值为n-1,因为我们要返回l,所以将r更新为mid-1不断缩小区间最终找到最小值返回*/int l 0,r nums.length-1;int n nums.length;while(l r){int mid l (r-l)/2;if(nums[mid]nums[n-1]){ //r mid - 1;}else {l mid 1;}}return nums[l];}
}4 寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 1
输入nums1 [1,3], nums2 [2]
输出2.00000
解释合并数组 [1,2,3] 中位数 2示例 2
输入nums1 [1,2], nums2 [3,4]
输出2.50000
解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5提示
nums1.length mnums2.length n0 m 10000 n 10001 m n 2000-106 nums1[i], nums2[i] 106
思路
解题思路
将求两个有序数组的中位数问题转化为求两个数组合并后第k小的数的问题。利用二分查找的思想每次排除一定数量的元素逐步缩小搜索范围直到找到第k小的数。
边界情况考虑
当其中一个数组到达边界时 如果已经到达数组nums1的边界此时要求的第k小的元素即为nums2开始的第k个直接返回nums2[index2 k - 1]。同理如果已经到达数组nums2的边界返回nums1[index1 k - 1]。 当k 1时 需要找到两个数组中第 1 小的数直接返回两个数组开头的最小值。
具体实现步骤
求中位数的主方法 首先计算两个数组的长度m和n。如果合并后的数组大小为奇数直接求第(m n)/2 1小的数即可将结果强制转换为double类型后返回。如果合并后的数组大小为偶数那么需要求解第(m n)/2和第(m n)/2 1小的数然后取平均并返回。 求第k小的数的辅助方法 初始化两个数组的指针index1和index2分别指向nums1和nums2的起始位置。进入一个循环在循环中不断缩小搜索范围直到找到第k小的数。在每次循环中首先判断边界情况 如果到达nums1的边界返回nums2[index2 k - 1]。如果到达nums2的边界返回nums1[index1 k - 1]。如果k 1返回两个数组开头的较小值。 正常处理时为了后续比较的方便先求出A[k/2 - 1]和B[k/2 - 1]的下标但要注意不能直接index k/2 - 1可能会越界应该使用Math.min(index k/2, array.length) - 1来计算。判断nums1[newIndex1]和nums2[newIndex2]的大小 如果nums1[newIndex1] nums2[newIndex2]说明可以排除掉nums2中[index2,...,index2 k/2 - 1]的部分更新index2 index2 k/2同时更新k的值为k - newIndex2 - index2 1。如果nums1[newIndex1] nums2[newIndex2]可以排除掉nums1中[index1,...,index1 k/2 - 1]的部分更新index1 index1 k/2更新k的值为k - newIndex1 - index1 1。
五、算法复杂度分析
时间复杂度 由于每次循环都将搜索范围缩小一半所以时间复杂度为O(logn)其中m和n分别是两个数组的长度。 空间复杂度 算法只使用了几个额外的变量不随输入规模增长而增长所以空间复杂度为O(1)。
代码
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {/**使用求两个数组中第k小的数来求解中位数。两种情况1.合并后的数组大小为奇数num则直接求第 num/21 小的数即可2.合并后的数组大小为偶数num那么需要求解第 num/2 和第num/21小的数然后再取平均*/int m nums1.length,n nums2.length;if((mn)%2!0){int mid getKthElement(nums1,nums2,(mn)/21);return (double)mid;}else{double mid1 getKthElement(nums1,nums2,(mn)/2);double mid2 getKthElement(nums1,nums2,(mn)/21);return (mid1mid2)/2;}}/**转换为求两个数组中第k小的数因为时间复杂度需要为O(log(mn)),因此考虑二分查找的办法。每次排除都排除k/2个元素。假设有A,B两个数组现在要求A,B数组合并后的第k小的数求A[k/2-1] B[k/2-1]的值判断这两个的大小1.若A[K/2-1] B[k/2-1]说明B[0,...,k/2-1]中的k/2个数一定不会是第k小的数所以更新B的下标排除B[0,...,k/2-1]2.反之若A[k/2-1] B[k/2-1] 说明A[0,...,k/2-1]中的k/2个数一定不会是第k小的数所以更新A的下标排除A[0,...,k/2-1]相等的话排除A和B都行这里排除A在排除A/B的k/2个元素后我们现在需要在新的数组中找到第k - k/2 小的元素因此更新k k-k/2注意边界条件1.假如已经到达A/B数组的边界以A为例已经到达数组A的边界此时要求的第k小的元素即为B开始的第k个直接返回B[index k - 1],反之则返回A[indexk-1]2.假如k1需要找到两个数组中第1小的数直接返回两个数组开头的最小值*/private int getKthElement(int nums1[],int nums2[],int k){int index1 0,index2 0;while(true){//1.判断边界条件//1.1 到达数组1的边界,返回数组2中第k小的数if(index1nums1.length){return nums2[index2k-1];}//1.2 到达数组2的边界返回数组1中第k小的数if(index2nums2.length){return nums1[index1k-1];}//1.3 k1需要找到两个数组中第1小的数,直接取两个数组中index较小的数if(k1){return Math.min(nums1[index1],nums2[index2]);}//2.正常处理// 2.1 为了后续比较的方便先求出A[k/2-1]和B[k/2-1]的下标// newIndex1 等价于 A的k/2-newIndex2 等价于B的k/2-1// 注意直接indexk/2-1会越界所以不能这样。// int newIndex1 index1 k/2 - 1;// int newIndex1 index2 k/2 -1;int newIndex1 Math.min(index1k/2,nums1.length)-1;int newIndex2 Math.min(index2k/2,nums2.length)-1;//2.2 判断A[k/2-1]和B[k/2-1]的大小即判断A[pivot1]和B[pivot2]的大小//2.2.1 nums1[k/2-1] nums2[index2 k/2-1],可以排除掉nums2中[index2,...,index2k/2-1]的部分更新index2 index2 k/2,同时更新k的值if(nums1[newIndex1]nums2[newIndex2]){//1更新k的值k - newIndex2-index21;//2排除掉后更新index2的值index2 newIndex21;}else {//2.2.2 nums1[k/2-1] nums2[index2 k/2-1],可以排除掉nums1中[index1,...,index1k/2-1]的部分更新index1 index1 k/2// 注意这里等于的情况放在哪里都可以。//1更新k的值k - newIndex1 - index1 1;//2排除掉后更新index1的值index1 newIndex1 1;}// ×2.2.3 更新k因为已经排除掉了k/2个元素现在只需要求k-k/2小的值,// k k - k/2;}}
}
