搜索旋转数组相关

189.旋转数组、寻找旋转排序数组中的最小值 I、寻找旋转排序数组中的最小值 II、搜索旋转排序数组 I、搜索旋转排序数组 II、面试题 10.03.搜索旋转数组

189.旋转数组

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k = k%n;

        //先整个翻转
        reverse(nums, 0, n-1);
        //翻转前k个
        reverse(nums, 0, k-1);
        //翻转后n-k个
        reverse(nums, k, n-1);
    }
    void reverse(vector<int>& nums, int start, int end){
        while(start<end){
            int temp=nums[start];
            nums[start++]=nums[end];
            nums[end--]=temp;
        }
    }
};

153.寻找旋转排序数组中的最小值 I

class Solution {
public:
    int findMin(vector<int>& nums) {
        //数组中最后一个元素，最小值右边的一定比它小，最小值左边的一定比它大
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(left < right){
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[right]){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return nums[left];
    }
};

154.寻找旋转排序数组中的最小值 II

class Solution {
public:
    int findMin(vector<int>& nums) {
        //数组中最后一个元素，最小值右边的一定比它小，最小值左边的一定比它大
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>nums[right]){
                left=mid+1;
            }else if(nums[mid]<nums[right]){
                right=mid;
            }else{
                //将right左移一位
                right=right-1;
            }
        }
        return nums[left];
    }
};

33.搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        if(n==0) return -1;

        int left=0;
        int right=n-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return mid;

            //右半部分是有序的
            if(nums[n-1]>nums[mid]){ 
                //target落在右半部分有序区域内
                if(nums[mid]<target && target<=nums[n-1]){
                    left = mid+1;
                }else{ //target落在左半部分无序区域内
                    right = mid-1;
                }
            }else{//左半部分是有序的
                //target落在左半部分有序区域内
                if(nums[0]<=target && target<nums[mid]){
                    right = mid-1;
                }else{
                    //target落在右半部分无序区域内
                    left = mid+1;
                }
            }
        }
        return -1;
    }
};

//解法二
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        int k=1;
        while(k<n && nums[k] >= nums[k-1]) k++;
        int res=-1;

        int left_val = BinarySearch(nums, target, 0, k-1);
        int right_val = BinarySearch(nums, target, k, n-1);

        if(left_val!=-1) res=left_val;
        if(right_val!=-1) res=right_val;

        return res;
    }
    //二分查找
    int BinarySearch(vector<int>& nums, int target, int low, int high){
        int n=nums.size();
        int left=low;
        int right=high;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]==target) return mid;
            else if(nums[mid]>target) right=mid-1;
            else left=mid+1;
        }
        return -1;
    }
};

81.搜索旋转排序数组 II

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n=nums.size();
        if(n==0) return false;
        int left=0;
        int right=n-1;
        while(left<=right){
            //重点在于处理重复数字
            //左边有重复数字，将左边界右移
            while(left<right && nums[left]==nums[left+1]) left++;
            //右边有重复数字，将右边界左移
            while(left<right && nums[right]==nums[right-1]) right--;
            int mid=left+(right-left)/2;
            if(nums[mid]==target) return true;
            //左半部分是有序
            if(nums[0]<=nums[mid]){
                //target落在左半部分有序区域内
                if(nums[0]<=target && target<nums[mid]){
                    right = mid-1;
                }else{
                    //target落在右半部分无序区域内
                    left = mid+1;
                }
            }else{ //右半部分是有序
                //target落在右半部分有序区域内
                if(nums[mid]<target && target<=nums[n-1]){
                    left = mid+1;
                }else{
                    //target落在左半部分无序区域内
                    right = mid-1;
                }
            }
        }
        return false;
    }
};

面试题 10.03.搜索旋转数组

class Solution {
public:
    int search(vector<int>& arr, int target) {
        int n=arr.size();
        int left=0;
        int right=n-1;
        while(left<=right){
            //当left符合时直接返回，因为找的是最小的索引
            if(arr[left]==target) return left;

            int mid=left+(right-left)/2;
            //当中间值等于target，将右边界移到中间，因为左边可能还有相等的值
            if(arr[mid]==target){
                right=mid;
            }else if(arr[0]<arr[mid]){      //左半部分是有序
                //target落在左半部分有序区域内
                if(arr[0]<=target && target<arr[mid]){
                    right = mid-1;
                }else{
                    //target落在右半部分无序区域内
                    left = mid+1;
                }
            }else if(arr[0]>arr[mid]){ //右半部分是有序
                //target落在右半部分有序区域内
                if(arr[mid]<target && target<=arr[n-1]){
                    left = mid+1;
                }else{
                    //target落在左半部分无序区域内
                    right = mid-1;
                }
            }else{
                //当中间数字与左边数字相等时，将左边界右移
                left=left+1;
            }
        }
        return -1;
    }
};