企业官网建设流程全解析

淄博便宜网站设,如何做与别人的网站一样的,wordpress 友情链接,织梦免费网站模块下载题目描述 整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。 在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 向左旋转#xff0c;使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0…题目描述整数数组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解决方案核心逻辑代码利用旋转数组「被最小值拆分为两个独立升序子数组」的特性把复杂的旋转数组查找拆解为两步找分割点通过findMin函数用二分法找到数组最小值的索引即两个升序子数组的分割点分区间查找根据target与数组最后一个元素的大小关系判断target属于左侧还是右侧升序子数组再通过lower_bound函数在对应有序区间内用二分法查找目标值最终返回结果。总结核心策略将旋转数组查找拆解为「找分割点 有序区间二分」把无序问题转化为有序问题解决关键设计全程使用开区间二分法循环条件left 1 right简化边界处理避免越界效率保障两次二分查找均为O(log n)整体保持对数级时间复杂度高效且稳定。函数源码class Solution { int findMin(vectorint nums) { int left -1, right nums.size() - 1; // 开区间 (-1, n-1) while (left 1 right) { // 开区间不为空 int mid left (right - left) / 2; if (nums[mid] nums.back()) { right mid; } else { left mid; } } return right; } // 有序数组中找 target 的下标 int lower_bound(vectorint nums, int left, int right, int target) { while (left 1 right) { // 开区间不为空 // 循环不变量 // nums[right] target // nums[left] target int mid left (right - left) / 2; if (nums[mid] target) { right mid; // 范围缩小到 (left, mid) } else { left mid; // 范围缩小到 (mid, right) } } return nums[right] target ? right : -1; } public: int search(vectorint nums, int target) { int i findMin(nums); if (target nums.back()) { // target 在第一段 return lower_bound(nums, -1, i, target); // 开区间 (-1, i) } // target 在第二段 return lower_bound(nums, i - 1, nums.size(), target); // 开区间 (i-1, n) } };