081 Search in Rotated Sorted Array II 搜索旋转排序数组 ||
2024-10-21 15:41:23
这是 “搜索旋转排序数组”问题的跟进:
如果数组元素允许重复，怎么办？
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
假设按照升序排序的数组在预先未知的某个关键点上旋转。
(例如， 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2）。
编写一个函数来判断给定的目标是否在数组中。
该数组可能包含重复项。
详见：https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/
Java实现：
class Solution {
public boolean search(int[] nums, int target) {
int n=nums.length;
if(n==0||nums==null){
return false;
}
int left=0;
int right=n-1;
while(left<=right){
int mid=(left+right)>>1;
if(nums[mid]==target){
return true;
}else if(nums[left]==nums[mid]&&nums[mid]==nums[right]){
++left;
--right;
}else if(nums[left]<=nums[mid]){
if(nums[left]<=target&&target<nums[mid]){
right=mid-1;
}else{
left=mid+1;
}
}else{
if(target>nums[mid]&&target<=nums[right]){
left=mid+1;
}else{
right=mid-1;
}
}
}
return false;
}
}
最新文章
- 对 Serializable和Parcelable理解
- 《转》 浅谈C# 多态的魅力（虚方法，抽象，接口实现）
- requirejs：模块加载(require)及定义(define)时的路径小结
- 【linux】学习1
- QProgressBar的使用例子
- RTB
- PHP 表单验证 - 完成表单实例
- 回收进程用户空间资源 exit()函数 _exit()函数 atexit()函数 on_exit()函数
- PHP - mysql使用参数数据
- grails的controller和action那点事---远程调试groovy代码
- 《剑指Offer》面试题-从头到尾打印链表
- javascript代码实现简单的五星评价功能！
- Math类的方法应用
- c++ 入门 之 hello world 和基本语法
- LOJ 2551 「JSOI2018」列队——主席树+二分
- edu30F. Forbidden Indices
- Window对象属性
- libcurl断点下载遇到的问题
- 你应该知道的JAVA面试题
- Objective-C学习笔记（四）——OC实现最简单的数学运算