在这种情况下，如何找到数组的最小索引？ [英] How can I find the minimum index of the array in this case?

问题描述

我们得到了一个具有 n 个值的数组。

We are given an array with n values.

示例： [1 ，4,5,6,6]

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

For each index i of the array a ,we construct a new element of array b such that,

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

b[i]= [a[i]/1] + [a[i+1]/2] + [a[i+2]/3] + ⋯ + [a[n]/(n−i+1)] where [.] denotes the greatest integer function.

我们也给了整数 k 。

我们必须找到最小值 i ，以使 b [i]≤k 。

We have to find the minimum i such that b[i] ≤ k.

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

I know the brute-force O(n^2) algorithm (to create the array - 'b'), can anybody suggest a better time complexity and way solve it?

例如，对于输入 [1,2,3] ， k = 3 ，输出为 1（最小索引）。

For example, for the input [1,2,3],k=3, the output is 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（明显）

现在，我们必须找到索引 i 这样 b [i]< = k ， k ='3'和 b [1]< = 3 ，因此， 1 是我们的答案！ ：-)

Now, we have to find the index i such that b[i]<=k , k='3' , also b[1]<=3, henceforth, 1 is our answer! :-)

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

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

推荐答案

这里有一个 O（n√A）时间算法来计算 b 数组，其中 n 是 a 数组和 A 是 a 数组的最大元素。

Here's an O(n √A)-time algorithm to compute the b array where n is the number of elements in the a array and A is the maximum element of the a array.

此算法计算 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 ，

This algorithm computes the difference sequence of the b array (∆b = b[0], b[1] - b[0], b[2] - b[1], ..., b[n-1] - b[n-2]) and derives b itself as the cumulative sums. Since the differences are linear, we can start with ∆b = 0, 0, ..., 0, loop over each element a[i], and add the difference sequence for [a[i]], [a[i]/2], [a[i]/3], ... at the appropriate spot. The key is that this difference sequence is sparse (less than 2√a[i] elements). For example, for 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 。

We can derive the difference sequence from a subroutine that, given a positive integer r, returns all maximal pairs of positive integers (p, q) such that pq ≤ r.

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

See complete Python code below.

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))

这篇关于在这种情况下，如何找到数组的最小索引？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！