首页 > ACM题库 > LeetCode > LeetCode-Find Minimum in Rotated Sorted Array II题解
2014
11-19

LeetCode-Find Minimum in Rotated Sorted Array II题解

Find Minimum in Rotated Sorted Array II

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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.

The array may contain duplicates.

标签: Array Binary Search
分析

Java代码:

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        n = len(num)
        low = 0
        high = n-1
        while low < high:
            if num[low] < num[high]:
                return num[low]
            mid = int((low + high)/2)
            if num[mid] > num[high]:
                low = mid+1
            elif num[mid] == num[high]:
                low += 1
            else:
                high = mid
        return num[low]

  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。