《剑指offer刷题笔记》10、旋转数组的最小数字【c++详细题解】

逃离我推掉我的手 2021-07-25 01:17 212阅读 0赞

**题目**

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组  3 , 4 , 5 , 1 , 2 \{3,4,5,1,2\} 3,4,5,1,2为  1 , 2 , 3 , 4 , 5 \{1,2,3,4,5\} 1,2,3,4,5 的一个旋转，该数组的最小值为  1 1 1。

数组可能包含重复项。

**注意**：数组内所含元素非负，若数组大小为  0 0 0，请返回  − 1 −1 −1。

**样例**

输入：nums=[2,2,2,0,1]
    
    输出：0

**思路1**

**(遍历)** O ( n ) O(n) O(n)

原来的数组是一个升序的数组，然后我们把升序数组的前若干个元素搬到数组的末尾，让我们找出现在这个数组的最小值。其实就是升序数组的第一个值。

我们只需要比较相邻的两项，只要后面一项比前面一项要小，那么后面一项就是数组中的最小值。因为原数组是升序的，把原数组最开始的若干个元素搬到数组的末尾，**其图形符合下图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]  
**或者是这样的：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]  
只需返回数组**第一个元素**就是最小值。

**代码1**

class Solution { 
    public:
        int findMin(vector<int>& nums) { 
            if(nums.size() == 0)  return -1;
            for(int i = 0; i < nums.size() - 1; i++)
            { 
                if(nums[i] > nums[i+1])  return nums[i+1];
            }
            return nums[0];
        }
    };

**思路2**

**(二分)** O ( n ) O(n) O(n)  
为了便于分析，我们先将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]  
图中水平的实线段表示相同元素。

我们发现除了最后水平的一段（黑色水平那段）之外，其余部分满足二分性质：竖直虚线左边的数满足  n u m s \[ i \] ≥ n u m s \[ 0 \] nums\[i\]≥nums\[0\] nums\[i\]≥nums\[0\]；而竖直虚线右边的数满足 n u m s \[ i \] < n u m s \[ 0 \] nums\[i\]< nums\[0\] nums\[i\]<nums\[0\]。  
分界点就是整个数组的最小值。

所以我们先将最后水平的一段删除即可。

另外，不要忘记处理数组完全单调的特殊情况：

*  当我们删除最后水平的一段之后，如果剩下的最后一个数大于等于第一个数，则说明数组完全单调。

**时间复杂度分析**  
二分的时间复杂度是  O ( l o g n ) O(logn) O(logn)，删除最后水平一段的时间复0杂度最坏是  O ( n ) O(n) O(n)，所以总时间复杂度是  O ( n ) O(n) O(n)。

**图示**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]  
`ans`就是我们最终**二分的边界**。

**代码2**

在class Solution { 
    public:
        int findMin(vector<int>& nums) { 
            int n = nums.size() - 1;
            if (n < 0) return -1;
            while (n > 0 && nums[n] == nums[0]) n -- ; //将最后水平的一段删除
            if (nums[n] >= nums[0]) return nums[0];  //说明数组完全单调
            int l = 0, r = n;
            while (l < r) { 
                int mid = l + r >> 1;       // [l, mid], [mid + 1, r]
                if (nums[mid] < nums[0]) r = mid;
                else l = mid + 1;
            }
            return nums[r];
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/5fb6f8bed25c4c8aa515b63ed24e6958.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/85092bc0f6ff491aa20a57818b9cb44c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/9abc39a066a54e8ca73438e1e6c2c140.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]: /images/20210724/4d4bfca364584dedaff805ec9ca1430e.png