【剑指offer】10.旋转数组的最小数字
程序员文章站
2022-06-17 19:54:06
...
直观解法并不难。从头到尾遍历数组,就能找到最小元素。但是时间复杂度是O(N),但是没有用到旋转数组的特性。
二分查找解法
注意到旋转之后的数组分为了两个有序的子数组。且前面的元素都大于或等于后面的子数组。而且最小值正好是两个子数组的分界线。考虑二分查找。
- 用两个指针分别指向数组的第一个元素和最后一个元素。(第一个元素应该大于等于最后一个元素)
- 然后寻找中间的元素。
- 如果该元素位于前面的子数组,它应该大于头指针,那么最小值应该位于它后面。可将头指针指向它
- 如果该元素位于后面的子数组,它应该小于头指针,那么最小值应该位于它前面。可将尾指针指向它
- 重复3 4
- 最后头指针应该指向前面子数组的最后,尾指针应该指向后面子数组的第一个。
- 返回尾指针
python
def findMin(self, nums: List[int]) -> int:
min_pos = 0
max_pos = len(nums) - 1
mid_pos = min_pos
while(nums[min_pos]>nums[max_pos]):
if max_pos - min_pos == 1:
mid_pos = max_pos
break
mid_pos = ( min_pos + max_pos ) // 2
if nums[mid_pos]>=nums[min_pos]:
min_pos = mid_pos
else:
max_pos = mid_pos
return nums[mid_pos
C++
int findMin(vector<int>& nums) {
int head = 0;
int nail = nums.size()-1;
int mid = head;
while(nums[head]>nums[nail]){
if(nail-head==1){
mid = nail;
break;
}
mid = (head+nail)/2;
if(nums[mid]>nums[head]){
head = mid;
}
else{
nail = mid;
}
}
return nums[mid];
}
上一篇: 一加BudsZ2什么时候上市?一加BudsZ2上市时间介绍
下一篇: 栈实现中序遍历二叉树