首页 > 代码库 > 简单的算法题, 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实现。