今日面试题:绳子的长度

一根一米长的绳子,随机断成三段;求最短的一段的期望长度以及最长的一段的期望长度。

================================

找数组的波谷分析:

原题

一个数组A[1...n],满足A[1]>=A[2], A[n] >= A[n-1]。A[i]被成为波谷,意味着:A[i-1] >= A[i] <= A[i+1]。请给出一个算法,找到数组中的一个波谷。O(n)的方法,是很直接,有更快的方法么?

分析

这个题目遍历一遍数组,显然就可以找到全部的波谷。时间复杂度O(n),空间复杂度是O(1)。但是如果我们只需要找到一个波谷,是否有更快的方法呢?更快的方法O(1)是不可能的,那只有O(logn),自然就想到二分查找。这个题目如果进行二分呢?我们看下面的数组A:

0 1 2 3 4 5 6
9 7 7 2 1 3 7
left mid right

A[0]>A[1],A[6]>A[5],满足题目中要求数组的条件。满足这样的条件,数组中一定是存在波谷的。假设不存在波谷,则A[0]

上表中的mid=3,A[mid]=2。A[mid-1]

0 1 2 3 4 5 6
9 7 7 2 1 3 7
left mid right

此时,mid满足波谷的条件,找到波谷。

总结上面的思路,找到数组的mid元素,mid有几种情况:

如果A[mid-1]>=A[mid] && A[mid+1]>=A[mid],找到波谷;

如果A[mid-1]<=A[mid]

如果A[mid+1]<=A[mid]

如果A[mid-1]

进一步分析

如果这个题目中,没有A[1]>=A[2]以及A[n]>=A[n-1]的约束,还能够以O(logn)的时间复杂度完成么?关键点就在于,中间的元素与其相邻的元素进行大小比较的时候,还能否选择一边继续进行查找。当A[mid-1]<=A[mid]时,可能是A[1]

T(n)=2T(n/2)+1

根据主定理,解得,时间复杂度为O(n).此时,是不存在O(logn)的。

本文来自微信:待字闺中,2013-07-23发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。