《剑指offer》--011--旋转数组中的最小数字

ゝ一世哀愁。 2022-06-01 05:47 141阅读 0赞

[《剑指offer》–目录索引][offer]

**题目：**

> 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。  
> 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组  
> \{3, 4, 5, 1, 2\}为\{1, 2, 3, 4, 5\}的一个旋转，该数组的最小值为1。

**思路：**

> 最简单直接的方法就是顺序查找，时间复杂度为0(n)，但是这样就没有用到旋转数组的特性了，而且这道题的最优解法的时间复杂度是接近O(log n)的；因此，首先来梳理一下旋转数组的特性：  
> ①无重复数字的旋转数组：第一个数字一定大于最后一个数字；  
> ②有重复数字的旋转数组：第一个数字大于或等于最后一个数字；  
> ③旋转数组以最小值为中界值将数组分成左右两个升序的数组；  
> ④以第一个数字的下标left和最后一个数字的下标right开始向中间靠拢，类似二分查找；中间数字的下标为mid=(left+right)/2；  
> ⑤如果arr\[left\] <= arr\[mid\],说明中间值属于左半边升序数组，则left=mid;  
> 否则，如果arr\[right\] >= arr\[mid\]，说明中间值仍属于右半边升序数组,则right=mid;  
> ⑥当left和right相邻，则代表已找到，arr\[right\]就是最小值，如动图：  
> ![这里写图片描述][SouthEast]  
> **特殊情况：**  
> 数组\{1，0，1，1，1\}是数组\{0，1，1，1，1\}的一个旋转，如下图：  
> ![这里写图片描述][SouthEast 1]  
> left下标的数字是1，right下标的数字是1，mid下标的数字也是1，像这种情况就无法分出mid所指的1到底属于左半边数组还是右半边数组，因此当三个下标所指向的数字相同时，只能用顺序查找了。

**代码：**

int MinInArray(int* arr,int left,int right)//顺序查找
    {
        int result=arr[left];
        int i=left+1;
        for(;i <= right;i++)
        {
            if(result > arr[i])
            {
                result =arr[i];
            }
        }
        return result;
    }
    
    int MinInOrder(int* arr,int length)//旋转数组中的最小值
    {
        assert(arr && length > 0);//断言，不能传空指针以及数组大小必须大于0
        if(length == 1)//如果数组就一个元素，最小值就是它本身
        {
            return arr[0];
        }
        int left=0;
        int right=length-1;
        int mid=left;
    
        while(arr[left] >= arr[right])//左半边数组的值要大于右半边数组的值
        {
            if(right-left == 1)//如果left和right相邻，代表找到了
            {
                mid=right;
                break;
            }
            mid=(left+right)>>1;
    
            if(arr[left] == arr[mid] && arr[right] == arr[mid])//当三个下标所指向的值相同时，只能用顺序查找了
            {
                return MinInArray(arr,left,right);
            }
    
            if(arr[left] <= arr[mid])
            {
                left=mid;
            }
            else if(arr[right] >= arr[mid])
            {
                right=mid;
            }
        }
        return arr[mid];
    }

**测试代码：**

void test1()// 典型输入，单调升序的数组的一个旋转
    {
        int arr[]={
       3,4,5,1,2};
        int sz=sizeof(arr)/sizeof(arr[0]);
        printf("%d\n",MinInOrder(arr,sz));
    }
    
    void test2()// 有重复数字，并且重复的数字刚好的最小的数字
    {
        int arr[]={
       3,4,5,1,1,2};
        int sz=sizeof(arr)/sizeof(arr[0]);
        printf("%d\n",MinInOrder(arr,sz));
    }
    
    void test3() // 有重复数字，但重复的数字不是第一个数字和最后一个数字
    {
        int arr[]={
       3,4,5,1,2,2};    
        int sz=sizeof(arr)/sizeof(arr[0]);
        printf("%d\n",MinInOrder(arr,sz));
    }
    
    void test4()// 有重复的数字，并且重复的数字刚好是第一个数字和最后一个数字
    {
        int arr[]={
       1,0,1,1,1};
        int sz=sizeof(arr)/sizeof(arr[0]);
        printf("%d\n",MinInOrder(arr,sz));
    
    }
    
    void test5() // 单调升序数组，旋转0个元素，也就是单调升序数组本身
    {
        int arr[]={
       1,2,3,4,5};
        int sz=sizeof(arr)/sizeof(arr[0]);
        printf("%d\n",MinInOrder(arr,sz));
    }
    
    void test6() // 数组中只有一个数字
    {
        int arr[]={
       2};
        int sz=sizeof(arr)/sizeof(arr[0]);
        printf("%d\n",MinInOrder(arr,sz));
    }
    
    void test7() // 数组中只有一个数字
    {
        printf("%d\n",MinInOrder(NULL,0));
    }
    
    int main()
    {
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
        return 0;
    }

**运行结果：**

![这里写图片描述][SouthEast 2]

[offer]: http://blog.csdn.net/w_y_x_y/article/details/79209805
[SouthEast]: /images/20220601/c5f3f2b19e0b4b2ca557c4d65926ecf0.png
[SouthEast 1]: /images/20220601/c7bff40ffae74d9484ee057ef764334c.png
[SouthEast 2]: /images/20220601/c31d2f2a24ac4c129eabd9e089627ef7.png