忻州集团网站建设,电商网站的多选菜单插件,微信开发者工具的介绍,酒店协会网站集静态模板题目描述
整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 旋转#xff0c;使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], n…题目描述
整数数组 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
解答
class Solution {
public:// 采用二分法int search(vectorint nums, int target) {int l 0, r nums.size() - 1;while(l r){int mid (l r) 1;if(target nums[mid]) return mid;// 旋转后产生左右两个升序序列// l ~ mid 都在左边的升序序列中if(nums[l] nums[mid]){// 范围确定在[l, mid)if(target nums[l] target nums[mid]) r mid - 1;// target nums[l] || target midelse l mid 1;}else // l~mid 一部分在左边一部分在右边{if(target nums[mid] target nums[r]) l mid 1;else r mid - 1;}}return -1;}int search1(vectorint nums, int target) {vectorint::iterator iter find(nums.begin(), nums.end(), target);return iter ! nums.end() ? iter - nums.begin() : -1;}
};
