资讯专栏INFORMATION COLUMN

leetcode 81 Search in Rotated Sorted Array II

Cheriselalala / 1270人阅读

摘要:题目要求相比于,中添加了数组中可能存在重复值的条件。这是我们可以将情况分为以下几种。因为如果而且,则左侧或右侧的子数组至少有一个为顺序的数组,这违背题目要求。所哟一定是同理,如果,那么。

题目要求
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

相比于I,II中添加了数组中可能存在重复值的条件。大家可以先参考一下我的这篇关于I的博客,在这个基础上,考虑如何实现这道题目。

思路与代码

在上一道题目的基础上,我们知道,如果数组中存在重复值,可能会出现类似于[1,3,1,1]这种情况出现。如果在这时候使用二分法,很可能会无法判断出到底属于左半侧数组还是右半侧数组。这是我们可以将情况分为以下几种。

目标值位于左侧上升数组中,也就是说nums[left]

目标值位于右侧上升数组中,也就是说nums[mid]

其它情况

    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){
                return true;
            }else if(nums[left] < nums[mid]){
                if(target>=nums[left] && target<=nums[mid]){
                    right = mid-1;
                }else{
                    left = mid + 1;
                }
            }else if(nums[mid] < nums[right]){
                if(target>=nums[mid] && target<=nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            //判断左右节点是否为目标值,不是则分别调整
            }else{
                if(nums[left] == target || nums[right] == target){
                    return true;
                }else{
                    left++;
                    right--;
                }
            }
        }
        return false;
    }
简单优化

在第三种情况下,我们可以看到该类别满足nums[left]>=nums[mid]且nums[mid]>=nums[right]。这时候,我们可以分析一下,

如果nums[mid]>nums[right],那么nums[mid]=nums[left]。因为如果nums[mid]>nums[right]而且nums[mid]

同理,如果nums[mid],那么nums[mid]=nums[left]"。

nums[mid]=nums[left]=nums[right]!=target

代码如下:

    public boolean search2(int[] nums, int target){
        int left = 0 , right = nums.length-1;
        while(left<=right){
            int mid = ( left + right ) / 2;
            if(nums[mid] == target){
                return true;
            }else if(nums[left] < nums[mid]){
                if(target>=nums[left] && target<=nums[mid]){
                    right = mid-1;
                }else{
                    left = mid + 1;
                }
            }else if(nums[mid] < nums[right]){
                if(target>=nums[mid] && target<=nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
                
            //精华第三种场景
            }else if(nums[mid] > nums[right]){
                left = mid + 1;
            }else if(nums[mid] < nums[left]){
                right = mid - 1;
            }else{
                left++;
                right--;
            }
        }
        return false;
    }


想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/67230.html

相关文章

  • [Leetcode] Search in Rotated Sorted Array 搜索旋转有序数组

    摘要:如果左边的点比右边的大,说明这两个点之间有一个旋转点,导致了不再有序。因为只有一个旋转点,所以一分为二后,肯定有一半是有序的。 Search in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 mi...

    thursday 评论0 收藏0
  • [LintCode/LeetCode] Search in Rotated Sorted Arra

    摘要:找中点若起点小于中点,说明左半段没有旋转,否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无,就容易了。还是用二分法优化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...

    U2FsdGVkX1x 评论0 收藏0
  • leetcode33 search in rotated sorted array

    摘要:这里相比于思路一,更适用于目标节点在中间的情况,而思路一在目标节点分布在数组两侧会效率更高。 题目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 ...

    MkkHou 评论0 收藏0
  • leetcode 33 Search in Rotated Sorted Array

    摘要:如正常的升序排列应该是,,,,,,旋转过后可能就是,,,,,,。想法因为这是一个经过旋转的升序数组,我们可以将其看作两个升序的序列,,,和,,。如果在前一个序列,则从前面进行查找。如果在后面一个序列,则从最后一个元素开始查找。 题目详情 Suppose an array sorted in ascending order is rotated at some pivot unknown...

    diabloneo 评论0 收藏0
  • [Leetcode] Find Minimum in Rotated Sorted Array 找旋

    摘要:二分迭代法复杂度时间空间递归栈空间思路找旋转数组的起点,实际上类似找一个山谷,只要两边都比中间高就对了,这和这题很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...

    notebin 评论0 收藏0

发表评论

0条评论

Cheriselalala

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<