首页 > 代码库 > 简单的算法题, Find Minimum in Rotated Sorted Array 的Python实现。
简单的算法题, Find Minimum in Rotated Sorted Array 的Python实现。
简单的算法题, Find Minimum in Rotated Sorted Array 的Python实现。
题目:
Suppose a sorted array 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.
这是 LeetCode 上的一道算法题,题意是一个已经排序的数组,截断后重新拼接,找出数组中最小的数字。
这道题目用 Python 来实现的话太简单了。代码如下:
class Solution: # @param num, a list of integer # @return an integer def findMin(self, num): return min(num)
用了 Python 内置的 min 函数,提交后通过,耗时是:Runtime: 184 ms
完成后被吐槽:“你这样有意思么?”,额,的确很没意思。那就考虑优化一下吧。
Python 内置的 min 函数是会遍历整个数组的,时间复杂度为 O(n),不过这个数组本来是有序的了,所以可以稍微做点优化,代码如下:
class Solution: # @param num, a list of integer # @return an integer def findMin(self, num): for i in range(0, len(num)-1): if(num[i] > num[i+1]): return num[i+1] return num[0]
当找到第一个值小于它之前的数字的时候,就可以结束循环了。此时代码理论上的复杂度还是 O(n),但实际上是会快一点点的。
提交后通过,看测试结果,耗时是:Runtime: 164 ms,看来优化还是有点效果的,快了一点点。
还能不能在快一点呢?题目中提到的 Sorted (已排序),很容易让人想到使用二分法来查找,不过这个排序不是真的排序,是被截断过的,所以要稍微做些变通。尝试加入二分查找的代码如下:
class Solution: # @param num, a list of integer # @return an integer def findMin(self, num): i = 0 j = len(num)-1 while(i < j-1): point = int((i + j)/2) if(num[point] > num[i]): i = point if(num[point] < num[j]): j = point return min(num[0], num[i], num[j])
使用二分法不断逼近最小的数字,此时代码的时间复杂度为 O(log2n) ,提交后通过,看测试结果,耗时是:Runtime: 140 ms。效果还行。
这个结果应该是我能做到的最优结果了。
简单的算法题, Find Minimum in Rotated Sorted Array 的Python实现。