旋转数组

问题1

旋转数组最小数

原理

• 这类问题的本质是使用二分法，因为遍历的效率是O(n),二分的时间复杂度为log(n)。
• 二分之后，一半是有序一半是无序，最小值就隐藏在无序数组的一层。多次二分就可以找到最小值。

代码

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length-1;
        while (low<high){
            int mid = low+(high-low)/2;
            if(nums[mid]>nums[high]){
                low = mid+1;
            }else{
                high = mid;
            }
        }
        return nums[low];
    }
}

注意事项

• 只要抓住，最小的元素肯定在无序的一侧就迎刃而解了。
• 注意元素不能重复，重复的情况就不太一样了。

问题2

旋转数组最小数，包含重复数

原理

• 首先，考虑的还是二分查找。
• 其次，需要注意的是如果元素重复的情况，例如：1，2，2，2，2，2，2 这种情况原来的办法就不好使了，这个时候我们需要处理的是当nums[mid]==nums[high]的情况，high--就可以完美处理这个问题
• 最后，一定要考虑重复的情况。

代码

class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length-1;
        while (low<high){
            int mid = low+(high-low)/2;
            if(nums[mid]>nums[high]){
                low = mid+1;
            }else if(nums[mid]>nums[high]){
                high = mid;
            }else{
                high--;
            }
        }
        return nums[low];
    }
}

注意事项

• 考虑重复元素的处理high--

问题3

旋转数组寻找目标数

原理

• 本质上还是二分查找
• 情况一，nums[mid]==target 直接返回
• 情况二，nums[mid]<nums[high] 说明右半侧有序，直接找target在右半侧的位置
• 情况三，nums[mid]>nums[high]说明左半侧有序，直接找target在左半侧的位置

代码

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;

        while (low<=high){
            int mid = low+(high-low)/2;
            if (nums[mid]==target){
                return  mid;
            }
            // 右半边有序
            if (nums[mid]<nums[high]){
                if(nums[mid]<target&&target<=nums[high]){
                    low = mid+1;
                }else{
                    high = mid-1;
                }
            }else{
                if (nums[low]<=target&&target<nums[mid]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }
        }
        return -1;
    }
}

注意事项

• 注意low<=high 可以取到==
• 注意元素不能重复，重复的情况需要考虑问题4

问题4

旋转数组寻找目标数，包含重复数

原理

• 本质上还是二分查找
• 情况一，nums[mid]==target 直接返回
• 情况二，nums[mid]<nums[high] 说明右半侧有序，直接找target在右半侧的位置
• 情况三，nums[mid]>nums[high]说明左半侧有序，直接找target在左半侧的位置
• 情况四，nums[mid]==nums[high],high--

代码

class Solution {
    public boolean search(int[] nums, int target) {
        int low = 0;
        int high = nums.length-1;
        while (low<=high){
            int mid = low +(high-low)/2;
            if(nums[mid]==target){
                return  true;
            }
            if (nums[mid]<nums[high]){
                if (nums[mid]<target&&target<=nums[high]){
                    low = mid+1;
                }else{
                    high = mid-1;
                }
            }else if(nums[mid]>nums[high]){
                if (nums[low]<=target&&target<nums[mid]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }else {
               high--;
            }
        }
        return false;
    }
}

注意事项

• 原理和问题3一样，注意的点和问题2一样，需要考虑重复元素的情况，重复元素的情况high--

问题5

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置

原理

• 首先这个问题还是一个二分查找的问题，只不过这个问题是需要查找两个元素而已。
• 可以实现两个函数一个findleft，一个findright
• 和普通的二分查找的区别在于，查找的过程可能存在重复的目标元素，我们的目标是找到重复元素的minLeft 或者maxRight。

代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = binaryLeft(nums,target);
        if (left==-1){
            return new int[]{-1,-1};
        }
        int right = binaryRight(nums,target);
        return  new int[]{left,right};
    }

    private int  binaryLeft(int[] nums,int target){
        int low = 0;
        int high = nums.length-1;
        while (low<=high){
            int mid = low +(high-low)/2;

            if (nums[mid]<target){
                low = mid+1;
            }else if(nums[mid]>target){
                high = mid-1;
            }else if(nums[mid]==target){
                high = mid-1;
            }
        }
        if (low != nums.length && nums[low] == target) {
            return low;
        }
        return -1;
    }
    private int  binaryRight(int[] nums,int target){
        int low = 0;
        int high = nums.length-1;
        while (low<=high){
            int mid = low +(high-low)/2;

            if (nums[mid]<target){
                low = mid+1;
            }else if(nums[mid]>target){
                high = mid-1;
            }else if(nums[mid]==target){
                low = mid+1;
            }
        }
        return high;
    }
}

注意事项

• 需要分成找left和right两种情况，最好利用两个函数实现。
• 需要考虑各种边界
• 第一当只有一个元素的时候例如：{1}的时候；
• 第二需要考虑 找到和找不到的情况，如何判断找到呢？low!=nums.length&&nums[low]==target 说明找到了。
• 第三需要注意的是，如果left找不到那么right就不用找了的特殊情况

问题6

两个有序数组找中位数

原理

代码

注意事项