algorithm - 在这种情况下如何找到数组的最小索引？

Question

我们得到一个数组 n值(value)观。

示例:[1,4,5,6,6]

对于每个索引 i数组 a ，我们构造数组的新元素 b这样，

b[i]= [a[i]/1] + [a[i+1]/2] + [a[i+2]/3] + ⋯ + [a[n]/(n−i+1)]其中 [.]表示最大整数函数。

我们得到一个整数 k

我们必须找到最小值 i这样 b[i] ≤ k .

我知道蛮力O(n^2)算法(创建数组 - 'b')，任何人都可以建议更好的时间复杂度和解决方法吗？

例如，对于输入[1,2,3] , k=3 , 输出为 1(minimum-index) .

在这里，a[1]=1; a[2]=2; a[3]=3;

现在，b[1] = [a[1]/1] + [a[2]/2] + [a[3]/3] = [1/1] + [2/2] + [3/3] = 3;

b[2] = [a[2]/1] + [a[3]/2] = [2/1] + [3/2] = 3;

b[3] = [a[3]/1] = [3/1] = 3 (obvious)

现在，我们必须找到索引 i这样 b[i]<=k , k='3' , 还有 b[1]<=3 , 今后, 1是我们的答案! :-)

Constraints : - Time limits: -(2-seconds) , 1 <= a[i] <= 10^5, 1 <= n <= 10^5, 1 <= k <= 10^9

Answer 1

这是一个 O(n √A) 时间算法来计算 b 数组，其中 n 是 a 数组，A 是a 数组的最大元素。

该算法计算b数组的差分序列(Δb = b[0], b[1] - b[0], b[2] - b[1 ], ..., b[n-1] - b[n-2]) 并将 b 本身导出为累积和。由于差异是线性的，我们可以从 Δb = 0, 0, ..., 0 开始，遍历每个元素 a[i]，并添加差异[a[i]], [a[i]/2], [a[i]/3], ... 在适当位置的序列。关键是这个差分序列是稀疏的(少于2√a[i]个元素)。例如，对于 a[i] = 36，

>>> [36//j for j in range(1,37)]
[36, 18, 12, 9, 7, 6, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
>>> list(map(operator.sub,_,[0]+_[:-1]))
[36, -18, -6, -3, -2, -1, -1, -1, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

我们可以从一个子程序中导出差分序列，给定一个正整数 r，返回所有正整数的最大对 (p, q) 使得 pq ≤ r。

请参阅下面的完整 Python 代码。

def maximal_pairs(r):
    p = 1
    q = r
    while p < q:
        yield (p, q)
        p += 1
        q = r // p
    while q > 0:
        p = r // q
        yield (p, q)
        q -= 1


def compute_b_fast(a):
    n = len(a)
    delta_b = [0] * n
    for i, ai in enumerate(a):
        previous_j = i
        for p, q in maximal_pairs(ai):
            delta_b[previous_j] += q
            j = i + p
            if j >= n:
                break
            delta_b[j] -= q
            previous_j = j
    for i in range(1, n):
        delta_b[i] += delta_b[i - 1]
    return delta_b


def compute_b_slow(a):
    n = len(a)
    b = [0] * n
    for i, ai in enumerate(a):
        for j in range(n - i):
            b[i + j] += ai // (j + 1)
    return b


for n in range(1, 100):
    print(list(maximal_pairs(n)))

lst = [1, 34, 3, 2, 9, 21, 3, 2, 2, 1]
print(compute_b_fast(lst))
print(compute_b_slow(lst))