FB 刚电面

是跟leetcode一样的那个sorted array shift产生的array求最大值？还是如楼主所说的先增大后减小?如果是后者，没办法用binary search吧？
如 case1：1,2,3,4,2,1
    case2：1,2,4,3,2,1
这些情况都没办法判断啊。

kongkonglin 发表于 2014-12-8 03:17
是跟leetcode一样的那个sorted array shift产生的array求最大值？还是如楼主所说的先增大后减小?如果是后者 ...

后一种情况，先增大再减小。用RECURSION然后类似BINARY SEARCH，不过需要多加CHECK来判断找哪边。

kongkonglin 发表于 2014-12-8 17:17
是跟leetcode一样的那个sorted array shift产生的array求最大值？还是如楼主所说的先增大后减小?如果是后者 ...

如果把A[mid] 和 A[mid-1] 比较 不就能知道当前是增序列还是减序列了吗，贴一个代码求轻拍:
def findMax(self, num):
        L = 0
        R = len(num)-1
        while L < R:
            M = int((L+R)/2)
            if not (num[M] > num[L] and num[M] > num[R]):
                return max(num[L],num[R])
            if num[M] > num[M-1] and num[M] > num[M+1]: # reach maximam
                return num[M]
            elif num[M] > num[M-1]: # left array is monotonic increasing
                L = M+1
            else: # right array is monotonic decreasing
                R = M-1
        return max(num[L],max(num[R],num[M]))

sunraincyq 发表于 2014-12-8 01:09
最大值没有DUPLICATE, 其他数字可能有，不过不妨碍

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1

can we use binary search to do it in O(logN)?

sunraincyq 发表于 2014-12-8 01:08
唉，已经挂了，答的不好。

楼主你好，她们是直接发的拒信么？隔了多久？非常感谢如果能告知。

sunraincyq 发表于 2014-12-8 01:08
唉，已经挂了，答的不好。

楼主你好，她们是直接发的拒信么？隔了多久？非常感谢如果能告知。

wksora 发表于 2014-12-18 19:57
楼主你好，她们是直接发的拒信么？隔了多久？非常感谢如果能告知。

就两天左右时间，HR给我发的邮件

sunraincyq 发表于 2014-12-19 13:16
就两天左右时间，HR给我发的邮件

谢谢~ 祝你后面好运。

zhongneu 发表于 2014-12-17 14:29
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1

can we use binary search to do it in O(logN)?

我觉得有duplicates的话 worst case是O(n)

jidhuang 发表于 2014-12-8 22:46
如果把A[mid] 和 A[mid-1] 比较 不就能知道当前是增序列还是减序列了吗，贴一个代码求轻拍:
def findMax ...

你这个会array index out of bound吧？
L = 0, R = 1, M = 0