西安做网站优化公司报价,野花韩国视频在线观看免费高清,网站可以用cdr做吗,宁波seo网络优化哪家好题目#xff1a; 题解#xff1a;
本题比普通的寻找旋转排序数组中的最小值多了一个数组中的元素可以重复这一点。 这会时原来的思路出现一个漏洞#xff08;大家感兴趣可以看看我做普通版寻找旋转排序数组最小值的思路#xff09;#xff0c;就是旋转后的数组中的第二个…题目 题解
本题比普通的寻找旋转排序数组中的最小值多了一个数组中的元素可以重复这一点。 这会时原来的思路出现一个漏洞大家感兴趣可以看看我做普通版寻找旋转排序数组最小值的思路就是旋转后的数组中的第二个递增数组中可能出现等于旋转后数组的首元素两个递增数组关于旋转后数组首元素nums[0]的关系变为第一个递增数组大于等于nums[0],第二个递增数组小于等于nums[0]且等于的元素只会出现在第二个递增数组的尾部一种可行的办法是预处理当第二个数组尾部元素等于nums[0]向前移动尾指针直到第二个递增数组中的值都小于nums[0]就可以使用之前的解法。
int findMin(vectorint nums) {int l0,rnums.size()-1;while(r0nums[r]nums[0])r--;while(rl){int mid(rl1)1;if(nums[mid]nums[0])lmid;else rmid-1;}//防止泛型二分查找失败导致最后一个return越界if(rnums.size()-1)return nums[0];return min(nums[0],nums[r1]);} 题后反思
泛型二次查找会出现查找”失败的情况“当查找对象中全是0或者1的时候。当r,l指针是元素的位置的时候最好不要直接在查找之后的值上进行操作因为在查找失败后的操作容易越界。所以使用泛型二分查找后要判断一下是否查找成功。
