一个网站的tdk是指网站的,wordpress 简洁博客,手机号网站源码,wordpress 分页插件题目描述#xff1a;
已知存在一个按非降序排列的整数数组 nums #xff0c;数组中的值不必互不相同。
在传递给函数之前#xff0c;nums 在预先未知的某个下标 k#xff08;0 k nums.length#xff09;上进行了 旋转 #xff0c;使数组变为 [nums[k], nums[…题目描述
已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target 请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target 则返回 true 否则返回 false 。
你必须尽可能减少整个操作步骤。 示例 1
输入nums [2,5,6,0,0,1,2], target 0
输出true示例 2
输入nums [2,5,6,0,0,1,2], target 3
输出false 提示
1 nums.length 5000-104 nums[i] 104题目数据保证 nums 在预先未知的某个下标上进行了旋转-104 target 104 进阶
这是 搜索旋转排序数组 的延伸题目本题中的 nums 可能包含重复元素。这会影响到程序的时间复杂度吗会有怎样的影响为什么 通过次数
207.7K
提交次数
506.6K
通过率
41.0%
思路和题解
线性查找大家都会这里我们用二分法。
我们要知道的是只有顺序区间我们才能通过端点的值判断target是否在其中根据这个旋转数组的特性每次对这个数组进行二分二分后的两个区间至少有一个是顺序区间。对于无重复的旋转区间来说我们只需通过比较区间左端点的值left和右端点的值right就能判断这个区间是不是顺序区间对于这次有重复的旋转数组来说会出现nums[left]nums[mid]nums[right]的情况这是无法判断左右哪个是顺序区间需要将left和right都往内移。
代码
class Solution {
public://把要搜索的区间分为两部分对于这两部分总有一部分完全排序的bool search(vectorint nums, int target) {int lo0;int hinums.size()-1;int mid;while(lohi){mid(lohi)/2;if(nums[mid]target) return true;if(nums[lo]nums[mid]nums[mid]nums[hi]){lo;hi--;}else if(nums[lo]nums[mid]){if(nums[lo]targettargetnums[mid]){himid-1;}else{lomid1;}}else{if(nums[mid]targettargetnums[hi]){lomid1;}else{himid-1;}}}return false;;}
};
