leetcode33-- Search in Roted Sorted Array(被面过)

leetcode33-- Search in Roted 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,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

解答

这个题目中有个很强的假设,即里面的元素是不重复的,其实如果是不加旋转的话,就是一个简单的二分查找,但是现在不是单增的了,但是最关键的还是要确定下一步的search范围,即是search左边还是右边,所以可以这样做


class Solution(object):
    
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        if len(nums) == 0:
            return -1
        
        start, end = 0, len(nums)-1
        while start+1<end:
            mid = start+(end-start)/2
            if nums[mid]==target:
                return mid
            elif nums[mid] > nums[start]:
                if target>=nums[start] and target<=nums[mid]:
                    end = mid
                else:
                    start = mid
            else:
                if target>=nums[mid] and target<=nums[end]:
                    start = mid
                else:
                    end = mid
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        return -1

即看中间的位置上的值,分三大种情况,第一种就是直接找到了,第二种是像[3,4,5,6,7,8,9,0,1,2]的这种,即左边的偏重,这时候中间值是大于开始的值的,还有一种是右边的多 [8,9,0,1,2,3,4,5,6,7] , 在[3,4,5,6,7,8,9,0,1,2]这种情况下,要看target在哪个位置,如果nums[start]<=target<=nums[mid] 这种情况下,应该把右端点end=mid即转化为子问题了,其他的所有的情况都要把开始的位置更新start = mid.

第二种[8,9,0,1,2,3,4,5,6,7]情况下,也要看target在哪个位置,如果nums[mid]<=target<=nums[end] 这时候要把左边的更新成start=mid,其他的情况都要是end=mid

然后while结束的时候,说明start+1=end了,这时候只需要看这两个哪一个是的就可以了,如果都不是就返回-1.

用c++来写的话是这样的

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        
        int start=0, end = nums.size()-1;
        
        while(start+1<end){
            int mid = start+(end-start)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>nums[start]){
                if(nums[start]<=target && target<=nums[mid]){
                    end = mid;
                }else{
                    start = mid;
                }
            }else{
                if(nums[mid]<=target && target<=nums[end]){
                    start = mid;
                }else{
                    end = mid;
                }
            }
        }
        
        if(nums[start]==target) return start;
        if(nums[end]==target) return end;
        return -1;
    }
};

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦