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)
的算法解决此问题。
解题思路:
[4,5,6,7,0,1,2]这个示例我们来观察一下,首先它肯定具有二段性,两端递增的序列
A-B段:【4,5,6,7】 C-D段:【0,1,2】
我们以A点(min)为参照点:
- 当nums【mid】>=min的时候,left=mid+1
- 当nums【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. 点名
题目描述:
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records
。假定仅有一位同学缺席,请返回他的学号。
解题思路:
显然本题具有二段性,我们可以使用二分
- mid==record【mid】,left=mid+1;
- 当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; } };