东至网站制作,建筑网格布搭接,婚纱摄影照片,互联网公司经营范围有哪些一.题目要求
整数数组 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] 104 nums 中的每个值都 独一无二 题目数据保证 nums 在预先未知的某个下标上进行了旋转 -104 target 104
四.解题思路
首先二分递归查找到旋转边界。 而后将target和数组末位置比较决定是在左右哪个区间二分。
五.代码实现
class Solution {
public:int search(vectorint nums, int target) {int index dfs(nums, 0, nums.size() - 1);int l;int r;if (target *nums.rbegin()) {l 0;r index;} else {l index 1;r nums.size() - 1;}while (l r) {int m (l r) / 2;if (nums[m] target)return m;if (nums[m] target) {r m - 1;} elsel m 1;}return -1;}int dfs(vectorint nums, int left, int right) {if (left right || (left right) / 2 1 nums.size())return -1;if (nums[(left right) / 2] nums[(left right) / 2 1])return (left right) / 2;int a dfs(nums, left, (left right) / 2 - 1);int b dfs(nums, (left right) / 2 1, right);if (a ! -1)return a;if (b ! -1)return b;return -1;}
};六.题目总结
–
