LeetCode 81. Search in Rotated Sorted Array II（在旋转有序序列中搜索之二）

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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.

题目标签：Array

　　这道题目给了我们一个有序的array，其中是可以有重复的数字，让我们判断 target 是否在array里。这道题目和之前的那题基本思路一样，但是这里多了重复的数字，大部分情况下，不影响我们的程序，但是当我们遇到这种情况： 1，3，1，1，1 target = 3 当很多的重复数字rotate到了右边，并且占据了中间的位置，此时，我们就不能够判断出，应该选左边还是右边继续搜索了，因为mid == left 也 == right。所以我们要多加一个条件，把这种情况考虑进去，并且修改之前的条件。

　　case 1：如果left 小于 mid，说明左边是有序 array；

　　case 2：如果left 大于 mid，说明右边是有序 array；

　　case 3：如果left 等于 mid，而且当它们不在同一位置的时候，说明 mid 和 left 是重复项，并且右边应该全是重复项，此时可以把 left++，目的是让left 跳出重复项的范围。

　　这里只能left++，而不能right--，（针对于我的code），因为当 left 等于 mid，而且它们在同一位置的话，我们来看例子 1，3 target 是3的话：

　　　　　　　　left 指向1， mid 指向1， right 指向3，这里left 和 mid 重合了，而且我们每次遇到这种情况都是先 test left 的这一边，所以就要让left往右shift。

Java Solution:

Runtime beats 15.21%

完成日期：08/01/2017

关键词：Array

关键点：利用Binary Search 结合 rotated sorted array 中必然有一半是有序序列来搜索；当middle 等于 left 的情况下，让left++ 来跳出重复的数字范围

 public class Solution

 {

     public boolean search(int[] nums, int target)

     {

         if(nums == null || nums.length  == 0)

             return false;

         int left = 0;

         int right = nums.length - 1;

         while(left <= right)

         {

             int mid = left + (right - left) / 2;

             if(nums[mid] == target) // if the middle is the target, return true

                 return true;

             else if(nums[left] < nums[mid]) // meaning left half is ascending order

             {

                 if(target >= nums[left] && target < nums[mid]) // is target is in left half

                     right = mid - 1; // move to left half to search

                 else // target is in right half

                     left = mid + 1; // move to right half to search

             }

             else if(nums[left] > nums[mid])// meaning right half is ascending order

             {

                 if(target > nums[mid] && target <= nums[right]) // if target is in right half

                     left = mid + 1;

                 else // target is in left half

                     right = mid - 1;

             }

             else

                 left++;

         }

         return false;

     }

 }

参考资料：N/A

LeetCode 算法题目列表 - LeetCode Algorithms Questions List

巴特西

LeetCode 81. Search in Rotated Sorted Array II（在旋转有序序列中搜索之二）

最新文章

热门文章