今天分享leetcode第9篇文章,也是leetcode第153题—寻找旋转排序数组中的最小值,地址是:https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
【英文题目】(学习英语的同时,更能理解题意哟~)
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7]
might become [4,5,6,7,0,1,2]
).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2]
Output: 1
【中文题目】
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7]
可能变为 [4,5,6,7,0,1,2]
)。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
【思路】
本题也有两种思路:一是暴力破解,循环遍历甚至直接使用min函数时间复杂度为O(n);二是考虑使用类似二分查找的方法,时间复杂度为O(log n)。本文主要介绍第二种思路。
为了和二分查找进行比较,我们将最小的数称为target。
数组经过旋转后,会导致最小的数target在数组中间,比如[1, 2, 3, 4, 5]旋转后成为[3, 4, 5, 1, 2],target所在位置有什么特点呢?target右边的数(若存在)全部小于target左边的数(若存在)。
这样,我们使用二分查找的思想,找到一个数nums[mid],就可以和nums[0]进行比较,如果nums[mid] >= nums[0],则target只可能存在mid右边的区间内,反之则存在于mid左边的区间内,以此类推。
但是有一个特殊情况,就是旋转元素个数为0,需满足条件nums[0] < nums[length-1],直接返回nums[0]即可。
【代码】
python版本
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
l, r = 0, length - 1
# 旋转个数为0或者只有一个元素
if nums[l] <= nums[r]:
return nums[0]
else:
while l <= r:
mid = (l + r) // 2
# 只要nums[mid] >= nums[0],说明最小值还在mid后面
if nums[mid] >= nums[0]:
l = mid + 1
else:
r = mid - 1
return nums[l]
C++版本
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
// 旋转个数为0或者只有一个元素
if(nums[l] <= nums[r])
return nums[0];
while(l <= r){
int mid = (l + r) / 2;
// 只要nums[mid] >= nums[0],说明最小值还在mid后面
if(nums[mid] >= nums[0])
l = mid + 1;
else
r = mid - 1;
}
return nums[l];
}
};
【总结】
相关文章:
Search Insert Position(搜索插入位置)
给我好看