HelloKenLee

Leetcode 33 Search in Rotated Sorted Array 解题报告

Posted on By KenLee

题目信息

题目: 33. Search in Rotated Sorted Array

难度: Medium

正确率: 32.08%

问题描述:

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.

问题分析

  问题的大意是说,把一个升序的数组以某一个数为中心”旋转”以后得到一个数组,在这个数组中查找一个数,如果能查找到,就返回它的下标,如果不能查找到,就返回-1。   一开始我没怎么理解这个“旋转”的含义,其实就是说,选定一个数,然后把整一个数组循环左移(右移也行)到这个数作为第一个,把左移溢出的数放在数组右边。   比如[0,1,2,4,5,6,7],假设我们选择的数是4,那么“旋转的”过程如下:

	->[1,2,4,5,6,7,0] //把0循环左移,补到最右边
	->[2,4,5,6,7,0,1] //把1循环左移,补到0的右边
	->[4,5,6,7,0,1,2] //把2循环左移,补到1的右边,这时候4是第一位,结束。

解题思路

  首先这是一个查找问题,最简单的思路当然是扫一次出结果,时间复杂度为O(N)。我们且不提想要sort()一次再二分的那些自寻烦恼的思路(XD)。但是这种朴素的解法完全没有利用到题目给的信息,因为对于一个完全没有序的数组,我们也能扫一次出结果。因此这种解法肯定是TLE的。

  那么我们再观察一下样例数据,本身数组是有序的,经过了“旋转”之后尽管不是全局有序,但是起码是部分有序的,比如说第0位到第4位[4,5,6,7]是有序的,第5位到最后[0,1,2]也是有序的。那么一个简单的改进就是我扫前半部分[4,5,6,7],如果找到了,返回,如果没找到,则我知道后面的[0,1,2]也是有序的了,然后在后面的数据中采用二分查找。然而,这种解法尽管在最好的情况下是O(lgN),在平均和最坏的复杂度都是O(N),如无意外也是TLE的。

  上述的想法其实相当于把原数组分成了两部分[A,B],我们在A中使用扫描,在B中使用二分。那么能不能在A中也使用二分呢?因为原升序的数列可以写成[B,A],现在我们要进行查找的数列是[A,B],我们可以知道,B中的每一个数都比A小。 更确切来说,B中的每一个数都比A[0]小,A中的每一个元素都比A[0]大! 有了这个条件,如果我们要找一个数X,如果X小于A[0],我们就应该在B中进行二分查找,若大于A[0],我们则应该在A中进行查找。那么现在剩下的问题是,我们无法以常数时间区分A和B,因此,我们应该直接在整个数组中进行二分查找。和平时二分查找不同的是,假设我们要找的目标在A中,我们的mid命中了B中的数,我们应该把命中的数当作无限大处理;反之,如果我们命中了A的数,我们应该把它当作无限小来处理。举个例子:

	nums=[4,5,6,7,0,1,2];

  如果我们要查找的数比nums[0]=4小(比如1),我们相当于在[-oo,-oo,-oo,-oo,0,1,2]中查找;反正,如果我们要找的数比nums[0]=4大(比如6),我们相当于在[4,5,6,7,+oo,+oo,+oo]中进行查找。   分析:二分查找每一次选取一个mid来和target进行比较,每次名字比较一次,总体时间复杂度为O(log2(N));上述的二分查找除了需要和target比较以外,还需要和A[0]比较,因此最坏比较次数3次,时间复杂为O(3log2(N)),也就是O(lgN)。   这应该是比较优化的做法了,提交代码,最终通过时间为3ms,比80%的提交者优秀且和最佳成绩相差不足1ms,姑且认为是服务器状态差异。

主要数据结构

  - vector<int> nums:输入数组   - int target:需要查找的目标   - int left:二分查找左边界下标   - int right:二分查找右边界下标   - int midNum:二分查找的中间元素的值

源代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size();
        if(right==0)
            return -1;
        while(left<right){
            int mid=(left+right)/2;
            int midNum=nums[mid];
            if(nums[mid]>nums[0] && target<nums[0]){
                //要找的数比nums[0]小(比如上面的2)但是nums[mid]又比nums[0]大,比如上面的7,那我们把midNum看做-oo
                midNum=INT_MIN;
            }else if(nums[mid]<nums[0] && target>=nums[0]){
                //要找的数比nums[0]大,但是nums[mid]又比nums[0]小,那我们把midNum看做+oo
                midNum=INT_MAX;
            }
            if(target>midNum){
                left=mid+1;
            }else if(target<midNum){
                right=mid;
            }else{
                return mid;
            }
        }
        return -1;
    }
};