81.Search in Rotated Sorted Array II---二分变形
2024-09-02 04:23:50
题目大意:与33题类似,只是这里数组中有重复数值。
法一:解法与33题类似,只是这里要处理1,3,1,1,1这种情况,即有重复值时,mid与left和right都相等时,可以采用right--的方式错开相等值再比较。代码如下(耗时2ms):
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(nums[mid] == target || nums[left] == target || nums[right] == target) {
return true;
}
//如果左数组有序
else if(nums[left] < nums[mid]) {
//如果target在左数组中
if(target < nums[mid] && target > nums[left]) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
//如果右数组有序
else if(nums[mid] < nums[right]){
//如果target在右数组中
if(target < nums[right] && target > nums[mid]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
//如果出现1,3,1,1,1的情况,mid值与left和right都相等,则将right--再比较
else {
right--;
}
}
return false;
}
最新文章
- kali开启ssh
- find函数
- 使用Cyclone IV控制DDR2
- [Android NDK/JNI-1A]-开发环境搭建
- [转]Python核心模块——urllib模块
- javascript学习笔记(一)
- SQL Server中日志
- Servlet 笔记-异常处理
- 类相关的BIF
- vue--监听器
- BZOJ3196二逼平衡树——线段树套平衡树(treap)
- PHP设计模式注意点
- Linux学习6-CentOS搭建appium服务
- CodeWarrior WarningC12056
- Cisco交换机配置VLAN
- VSS2005 上传pdf 空白
- C语言 &#183; 关联矩阵
- luogu P1012 拼数
- 洛谷 P3225 [HNOI2012]矿场搭建
- Palindrome Function
热门文章
- BZOJ 1149 风铃(树形DP)
- BZOJ 1036 树的统计(树链剖分)
- [洛谷P4092][HEOI2016/TJOI2016]树
- POJ2135:Farm Tour——题解
- BZOJ1070:[SCOI2007]修车——题解
- BZOJ2527 &; 洛谷3527:[Poi2011]Meteors——题解
- 将Visual Studio项目转换为Dot Net Core项目 csproj to xproj
- POJ 2763 Housewife Wind 纯粹LCA写法(简单无脑)
- bzoj 1564 [NOI2009]二叉查找树 区间DP
- HDU3265 线段树(扫描线)