leetcode算法练习【81】搜索旋转排序数组 II

古城微笑少年丶 2023-02-12 02:25 15阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：二分法
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
    
    ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
    
    编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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

#### 方案：二分法 ####

*  参考33题，由于81是有重复的数组，则在获得节点的时候需要考虑nums\[start\] = nums\[end\]的情况，这时候我采用的是start++，而不是直接赋值，则这时候可以避免因为重复而引起的转换节点获取错误的问题

class Solution { 
            public boolean search(int[] nums, int target) { 
                    if (nums.length==0)return  false;
                    if (nums.length==1) return nums[0]==target?true:false;
                    int start = 0;
                    int end = nums.length-1;
                    while(start<end-1&&nums[start]>=nums[end]){ 
                        int mid = start+(end-start)/2;
                        if(nums[mid]<nums[start]) end = mid;
                        else if(nums[mid]>nums[start]) start = mid;
                        else if(nums[mid]==nums[start]) start++;
                    }
                    //获得了节点
                     if (nums[start]<nums[end]){ 
                        if (nums[0]>target||nums[nums.length-1]<target)return false;
                        return dicsearch(nums,0, nums.length-1,target);
                    }
        
        
                    else if(nums[start]<target||nums[end]>target) return false;
                    else if(nums[0]<=target)return dicsearch(nums,0,start,target);
                    else if (nums[nums.length-1]>=target)return dicsearch(nums,end,nums.length-1,target);
                    else return false;
                }
        
                public boolean dicsearch(int[] nums,int first,int last,int target){ 
                   if(first == last-1){ 
                        if(nums[last]>target&&nums[first]<target)return false;
                        else if (nums[last]==target) return true;
                        else if (nums[first]==target) return true;
        
                    }
                    int mid  = first+(last-first)/2;
                    if(nums[mid] == target) return true;
                    else if (nums[mid]>target) return dicsearch(nums,first,mid,target);
                    else if (nums[mid]<target)return dicsearch(nums,mid,last,target);
                    return  false;
                }
            }

##### 复杂度计算 #####

*  时间复杂度：O(logn)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode