哈尔滨网站推广公司哪家好,wordpress会员可见,福州app外包,泉州刺桐古建筑公司网站一#xff1a;题目
整数数组 nums 按升序排列#xff0c;数组中的值 互不相同 。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 旋转#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], 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 。
示例 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.因为题目说了这是一个升序的数组然后变成了旋转数组那么就可以用二分法 2.那么关于使用二分法这里分了两步 (1)利用nums[mid] 和 nums[0],来进行判断所分出的两部分中那一部分为有序的 如果nums[mid] nums[0]的话那么mid左边的序列为有序的 如果nums[mid] nums[0]的话那么mid右边为有序序列 (2):判断出有序序列后接下来就是判断target是否在该序列中 如果在左边有序的序列中 nums[l] target target nums[mid] 这时右边界条件就得进行变化r mid - 1; 否则 那么 target 就在 左边的无序列表当中那么的话我们就又要判断那部分是和 无序的和 nums[mid]进行比较。。。 和上方一致 如果在右边的有序序列中 nums[mid] target target nums[r] 这时左边界l mid 1; 否则类似上方
(3):注意(target和num[l])和(target和num[r]) 因为每次判断有序的范围是跟已 经判断target在哪个区间以内了所以需要更新比较的边界值
三上码 class Solution {
public:int search(vectorint nums, int target) {/**思路: 1.因为题目说了这是一个升序的数组然后变成了旋转数组那么就可以用二分法2.那么关于使用二分法这里分了两步(1)利用nums[mid] 和 nums[0],来进行判断所分出的两部分中那一部分为有序的如果nums[mid] nums[0]的话那么mid左边的序列为有序的如果nums[mid] nums[0]的话那么mid右边为有序序列(2):判断出有序序列后接下来就是判断target是否在该序列中如果在左边有序的序列中 nums[l] target target nums[mid]这时右边界条件就得进行变化r mid - 1;否则 那么 target 就在 左边的无序列表当中那么的话我们就又要判断那部分是和 无序的和 nums[mid]进行比较。。。。和上方一致如果在右边的有序序列中 nums[mid] target target nums[r]这时左边界l mid 1;否则类似上方 (3):注意(target和num[l])和(target和num[r]) 因为每次判断有序的范围是跟已 经判断target在哪个区间以内了所以需要更新比较的边界值 */int n nums.size();if(n 0){return -1;}if(nums[0] target){return 0;}int l 0;int r n - 1;int mid;while(l r){mid (l r)/2;if(nums[mid] target){return mid;}if(nums[mid] nums[l]){//左边序列是有序的if(target nums[l] target nums[mid]){r mid - 1;}else{l mid 1; }}else{//右边是有序的if(target nums[mid] target nums[r]){//target在右边的序列中l mid 1;}else{r mid - 1;}}}return -1;}
};加油 BOY!!!and girl
特别提醒 要特别注意本题的边界条件
