判断题 适中
#24880

假设数组a的值域范围是D,以下程序的时间复杂度是O(nlogn+nlogD)。 def check(n , a , k , dist): cnt = 1 las…

假设数组a的值域范围是D,以下程序的时间复杂度是O(nlogn+nlogD)。

def check(n , a , k , dist): 
    cnt = 1
    last = a [0]
    for i in range(1 , n):
        if a [i] - last >= dist : 
            cnt += 1
            last = a [i]
    return cnt >= k

def solve(n , a , k): 
    a_sorted = a .copy()
    a_sorted .sort()
    l = 0
    r = a_sorted [-1] - a_sorted [0]
    while l < r:
        mid = (l + r + 1) // 2
        if check(n , a_sorted , k , mid): 
            l = mid
        else:
            r = mid - 1
    return l

if __name__   == "__main__": 
    a = [1 , 2 , 8 , 4 , 9]
    n = 5
    k = 3
    result = solve(n , a , k)
    print(result)


未登录也能判分,登录后才会记录
答案与解析
正确答案:对
这道题暂未补解析。