【算法挨揍日记】day12——153. 寻找旋转排序数组中的最小值、LCR 173. 点名

ゞ浴缸里的玫瑰 2024-02-25 02:57 15阅读 0赞

![a2ead6fb123948888f1e0c4a672e1982.png][]

## 153. 寻找旋转排序数组中的最小值 ##

[153. 寻找旋转排序数组中的最小值][153.]

### 题目描述： ###

已知一个长度为 `n` 的数组，预先按照升序排列，经由 `1` 到 `n` 次 **旋转** 后，得到输入数组。例如，原数组 `nums = [0,1,2,4,5,6,7]` 在变化后可能得到：

*  若旋转 `4` 次，则可以得到 `[4,5,6,7,0,1,2]`
 *  若旋转 `7` 次，则可以得到 `[0,1,2,4,5,6,7]`

注意，数组 `[a[0], a[1], a[2], ..., a[n-1]]` **旋转一次** 的结果为数组 `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]` 。

给你一个元素值 **互不相同** 的数组 `nums` ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 **最小元素** 。

你必须设计一个时间复杂度为 `O(log n)` 的算法解决此问题。

### ![871fddbca8f24efd84df96931e2b6e79.png][] 解题思路： ###

> `[4,5,6,7,0,1,2]这个示例我们来观察一下，首先它肯定具有二段性，两端递增的序列`
> 
> `A-B段：【4,5,6，7】 C-D段：【0,1,2】`
> 
> ![9b3c1352332b4c068e07d0797efaeed0.png][]
> 
> 我们以A点(min)为参照点：
> 
>  *  当nums【mid】>=min的时候，left=mid+1
>  *  当nums【mid】<min的时候，right=mid
> 
> 但是有一种情况就是当它刚好选择n次，也就是变成了选择之前的样子，我们只需要在返回的时候判断left位置和min的大小返回其小值就可以了

### 解题代码： ###

class Solution {
    public:
        int findMin(vector<int>& nums) {
            int min=nums[0];
            int left=0,right=nums.size()-1;
            while(left<right)
            {
                int mid=left+(right-left)/2;
                if(nums[mid]<min) right=mid;
                else left=mid+1;
            }
            return nums[left]>min?min:nums[left];
        }
    };

--------------------

## LCR 173. 点名 ##

[LCR 173. 点名][LCR 173.]

### 题目描述： ###

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 `records`。假定仅有一位同学缺席，请返回他的学号。

![b898b1791bf5464d9be179ef138daf3c.png][]

### 解题思路： ###

> 显然本题具有二段性，我们可以使用二分
> 
>  *  mid==record【mid】，left=mid+1；
>  *  当mid<record【mid】，right=mid

### 解题代码： ###

class Solution {
    public:
        int takeAttendance(vector<int>& records) {
            int left=0,right=records.size()-1;
            while(left<right)
            {
                int mid=left+(right-left)/2;
                if(mid==records[mid]) left=mid+1;
                else right=mid;
            }
            return left==records[left]?left+1:left;
        }
    };

![200e2851a0df4f87899c891d7762c6f9.gif][]

[a2ead6fb123948888f1e0c4a672e1982.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/ffa22b1606d3413496a465b3f9bbe757.png
[153.]: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
[871fddbca8f24efd84df96931e2b6e79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/d24788690e204b85aa41fe6b8f90aa2f.png
[9b3c1352332b4c068e07d0797efaeed0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/885db973edd74d9b88ee830a9a5de0a2.png
[LCR 173.]: https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
[b898b1791bf5464d9be179ef138daf3c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/3e9d240e1cda4a1d9ce2675f67b1dccf.png
[200e2851a0df4f87899c891d7762c6f9.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/25/01e755f71a5c401f80dc8aa71cd11ab0.png