首页 > 试题广场 >

一篇文章有 n ( 1010000 )次,说明时间复杂度。(

[问答题]
一篇文章有 n 10<n<100 )个段落,第 i 个段落有 number[i] 个单词,设计算法,不得调用库函数,找出第 m 个单词属于第几个段落,查询共有 k k>10000 )次,说明时间复杂度。(段落编号从 0 开始)
def binarySearch(array, left, right, target):
    middle = (left + right)/2
    if array[middle] == target or array[middle]<target and array[middle+1]>target:
        return middle
    elif array[middle]>target:
        return binarySearch(array, left, middle-1, target)
    elif array[middle]<target:
        return binarySearch(array, middle+1, right, target)
def findithWord(number, m):
    tmp = [0,]
    for i in range(1, len(number)):
        tmp[i] = sum(number[:i+1])
    if m<tmp[1]:
        return 0
    if m>tmp[-1] and m<tmp[-1] + number[-1]:
        return len(number) - 1
    return binarySearch(tmp, 0, len(tmp), m)

发表于 2017-02-06 20:13:41 回复(0)