LeetCode Search in Rotated Sorted Array

· 1050 words · 3 minute read
2017年7月
LeetCode

33. Search in Rotated 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.

方法

对于搜索类型题目，若要优化可以使用二分搜索。

public class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                //若target为0，当nums[mid]为7时，则start = mid+1。当nums[mid]为2时，即nums[mid] < nums[0],则end = mid-1
                if(target < nums[0] && nums[mid] >= nums[0]){
                    start = mid+1;
                }else{
                    end = mid-1;
                }
            }else{
                //若target为6，当Snums[mid]为5时，start = mid + 1。当nums[mid]为0时，end = mid-1
                if(target > nums[nums.length-1] && nums[mid] <= nums[nums.length-1]){
                    end = mid-1;
                }else{
                    start = mid+1;
                }
            }
        }
        return -1;
    }
}

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?

方法

对于旋转数组中包含重复数，使用之前的算法会产生什么问题呢？举例： 777771237，target = 2，num[mid]=num[start]=num[end],之前的算法无效,即无法根据mid跟start和end的判断来确定是在数组的哪一部分。

解决方法也很简单，若遇到这种情况使end--,这样最后会找到num[mid]！=num[start]或者num[mid] != num[end]的情况，得解。

针对这类题型我觉得方法一不如方法二，方法二在逻辑概念上更加清晰。

  1. 首先判断num[mid]和num[start],num[end]的关系，若num[mid]=num[start]=num[end]，则end–。

  2. 在判断完mid属于哪一部分后再判断num[mid]和target的关系，target是在num[mid]的左边还是右边，然后选择是设置start还是end

    public class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        int mid = 0;
        while(start <= end){
            mid = (start + end) / 2;
            if(nums[mid] == target){
                return true;
            }
            //使用||而不是&&的原因是如1,3,mid = 0，即mid==start，若使用&&则进入不了判断，使用||则可以
            if(nums[mid] < nums[start] || nums[mid] < nums[end]){
                if(nums[mid] < target && target <= nums[end]){
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            //使用||原因同上
            }else if(nums[mid] > nums[start] || nums[mid] > nums[end]){
                if(nums[mid] > target && target >= nums[start]){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }
            }else{
                end--;
            }
        }
        return false;
    }
}

另外一个类似方法

在旋转数组中找最小值

public int minNumberInRotateArray(int [] array) {
        if(array.length == 0){
            return 0;
        }
        int start = 0;
        int end = array.length-1;
        int mid = start;
        //第一个元素大于或者等于最后一个元素
        while(array[start] >= array[end]){
            if(end-start == 1){
                mid = end;
                break;
            }

            mid = (start + end) / 2;
            //顺序查找
            if(array[start] == array[end] && array[end] == array[mid]){
                int result = Integer.MAX_VALUE;
                for(int i = start; i<= end; i++){
                    if(result > array[i]){
                        result = array[i];
                    }
                }
                return result;
            }
            //折半查找
            if(array[mid] >= array[start]){
                start = mid;
            }else if(array[mid] <= array[end]){
                end = mid;
            }
        }
        return array[mid];
    }
Share