81. Search in Rotated Sorted Array II

发表于 | 分类于

每日一题 2019 - 04 - 15

题目：

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

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

1
2
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

1
2
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

  • This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
  • Would this affect the run-time complexity? How and why?

思路：

这个题让找出给定的数组中某一个元素是否存在，这个数组原本是有序的但是经过了某一个位置进行了旋转，而且数组中的元素可能存在重复性；

思路比较直接，使用二分查找求解，每次都拿着当前状态下的 nums[mid]跟 nums[right] 作对比，如果：

  • nums[mid] > nums[right] 证明前半段序列为有序
  • nums[mid] > nums[right] 证明后半段序列为有序
  • nums[mid] == nums[right] 将 right 前移即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if ( nums[mid] == target) return true;
            if ( nums[mid] <  nums[right]) {
                if ( nums[mid] < target &&  nums[right] >= target) left = mid + 1;
                else right = mid - 1;
            } else if(nums[mid] >  nums[right]){
                if ( nums[left] <= target &&  nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
            else
            {
                right -- ;
            }
        }
        return false;
    }
};
0%
undefined