企业官网建设流程全解析

平台网站制作,网络平台维护 是什么工作,外国人做那个视频网站吗,开发网页多少钱LeetCode 面试经典 150_二分查找_搜索旋转排序数组#xff08;114_33_C_中等#xff09;题目描述#xff1a;输入输出样例#xff1a;题解#xff1a;解题思路#xff1a;思路一#xff08;二分查找#xff09;#xff1a;代码实现代码实现#xff08;思路一#xf…LeetCode 面试经典 150_二分查找_搜索旋转排序数组114_33_C_中等题目描述输入输出样例题解解题思路思路一二分查找代码实现代码实现思路一二分查找以思路一为例进行调试题目描述整数数组 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题解解题思路思路一二分查找1、因数组是通过旋转得到所以存在两个升序部分也可能只存在一个。我们采用二分查找的方法查找到mid中间坐标此时mid左右两侧必定是一侧有序一侧无序左侧包含mid右侧区间包含mid有序也可看做无序处理。① 我们首先判断nums[mid]是否等于target若相等则直接返回。② 若nums[mid] ! target。我们可通过nums[mid]与nums[left]的比较来判断左侧区域是否有序。nums[mid] nums[left]注意这里是当存在两个元素时 left mid。如[1,2]target2左侧有序,右侧无序,则需判断target是否在nums[left]~nums[mid]的区间内。若target在区间内则在左区间有序区间继续进行查找此时为普通的二分查找:right mid-1若target不在区间内则在右区间无需区间继续进行查找:left mid1nums[mid] nums[right]左侧无序,右侧有序,则需判断target是否在nums[mid]~nums[right]的区间内。若target在区间内则在右区间有序区间继续进行查找此时为普通的二分查找:left mid1。若target不在区间内则在左区间无需区间继续进行查找:right mid-1。③ 若leftright 则查找失败。例nums{4,5,6,7,0,1,2}target0;初始left 0, right 6, target 0中间元素 nums[mid] 7不等于目标值左侧有序target 不在左侧区间更新 left 4。第二次left 4, right 6中间元素 nums[mid] 1不等于目标值左侧有序target 在左侧区间更新 right 4。第三次left 4, right 4中间元素 nums[mid] 0等于目标值返回索引 4。2、复杂度分析① 时间复杂度O(logn)其中 n 为 nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。② 空间复杂度O(1) 。代码实现代码实现思路一二分查找classSolution{public:intsearch(vectorintnums,inttarget){intleft0,rightnums.size()-1;intmid;while(leftright){//计算中间元素的下标midleft(right-left)/2;//如果中间元素为目标值target则返回中间元素的下标if(nums[mid]target)returnmid;//判断左侧区间是否有序if(nums[left]nums[mid]){//若左侧有序则判断target是否存在左侧区间范围内存在则查找左侧区间否则查找右侧区间if(nums[left]targettargetnums[mid]){rightmid-1;}else{leftmid1;}//若右侧区间有序}else{//若右侧有序则判断target是否存在右侧区间范围内存在则查找右侧区间否则查找左侧区间if(nums[mid]targettargetnums[right]){leftmid1;}else{rightmid-1;}}}//如果查找不到target则返回-1return-1;}};以思路一为例进行调试#includeiostream#includevectorusingnamespacestd;classSolution{public:intsearch(vectorintnums,inttarget){intleft0,rightnums.size()-1;intmid;while(leftright){//计算中间元素的下标midleft(right-left)/2;//如果中间元素为目标值target则返回中间元素的下标if(nums[mid]target)returnmid;//判断左侧区间是否有序if(nums[left]nums[mid]){//若左侧有序则判断target是否存在左侧区间范围内存在则查找左侧区间否则查找右侧区间if(nums[left]targettargetnums[mid]){rightmid-1;}else{leftmid1;}//若右侧区间有序}else{//若右侧有序则判断target是否存在右侧区间范围内存在则查找右侧区间否则查找左侧区间if(nums[mid]targettargetnums[right]){leftmid1;}else{rightmid-1;}}}//如果查找不到target则返回-1return-1;}};intmain(intargc,charconst*argv[]){vectorintnums{4,5,6,7,0,1,2};inttarget0;//旋转排序数组Solution s;couts.search(nums,target);return0;}LeetCode 面试经典 150_二分查找_搜索旋转排序数组114_33)原题链接欢迎大家和我沟通交流(✿◠‿◠)