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

一尘不染

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

algorithm

给我们一个带有n值的数组。

例： [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就是我们的答案！:-)

限制条件：-时间限制：-( 2秒），1 <= a [i] <= 10 ^ 5，1 <= n <= 10 ^ 5，1 <= k <= 10 ^ 9

阅读 230

2020-07-28

共1个答案

一尘不染

这是一个O(n √A)用于计算b数组的-time算法，其中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))

2020-07-28