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

Question

我们有一个包含n个值的数组。

例如：[1,4,5,6,6]

对于数组a的每个索引i，我们构造一个新的数组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（最小索引）。

在这里，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就是我们的答案！ :-)

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

- sdrtg ghytui

---

问题不清楚。有多少个b数组被构建了？另外，为什么你从[a[i+1]/2]跳到了[a[i+3]/3]？请解释一下[1,2,3]的例子，并列出它的k（难道i不是以零为基础的索引吗？）。 - גלעד ברקן

[1/1] + [2/2] + [3/3] 不是等于3吗？ - גלעד ברקן

你有原问题的链接吗？这看起来很有趣 :) - Pham Trung

你确定它可以比O(n^2)更好地完成吗？ - Reaz Murshed

昨天也有人问过这个问题，但是没有解决方案。 - user3386109

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，返回所有满足pq≤r的正整数对(p,q)的最大值。

以下是完整的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))

- David Eisenstat

---

如果我们对于每个x=a[i]，执行x/1，x/2 ... ... x/n，那么它怎么可能是2*（x的平方根）？ - sdrtg ghytui

@Firexsecred 看看我为36计算的差分序列中有多少个零。鉴于差分序列的表示，我们不需要为这些做任何工作。 - David Eisenstat

首先，非常感谢您的大力贡献 :) 其次，假设数组'a'为[2,1,3]，现在我们如何使用上述算法计算'b'呢？您可以在上面的答案中添加对此示例的解释 :-) - sdrtg ghytui

@Firexsecred 我认为如果你翻转数组的话它会起作用。 - David Eisenstat

没错，: D 当我们颠倒数组时它能正常工作。最后一个问题，它适用于问题中提到的约束条件吗？ - sdrtg ghytui

Answer 2

这可能达不到David Eisenstat的答案效率，但是因为我花了相当长的时间来找出一种实现方法，所以我还是决定将它留下。目前看来，它大约是 O(n^2)。

b[i] 的元素可能无序，但它们的部分不是：

[a[1]/1] + [a[2]/2] + [a[3]/3]
           |------ s2_1 -----|
                      |-s1_1-|

           [a[2]/1] + [a[3]/2]
           |------ s2_2 -----|
                      |-s1_2-|

                      [a[3]/1]
                      |-s1_3-|


s2_1 < s2_2

s1_1 < s1_2 < s1_3

在s1上进行二分查找来查找k。任何一个s1_i大于k的结果都将排除一部分有序行（行是b_i）。

在剩下的行上，在s2上进行二分查找k。任何一个s2_i大于k的结果都将排除一部分有序行（行是b_i）。

这并不能很好地帮助我们，因为在最坏的情况下，我们会有O(n ^ 2 * log n)的时间复杂度，大于O(n ^ 2)。

但我们也可以水平搜索。如果我们知道b_i ≤ k，那么它将排除所有长度大于或等于该值的行，以及不需要搜索较小的s(m)s的需求，不是因为较小的s(m)s不能产生一个>= k的和，而是因为它们一定会产生更高的和我们正在寻找最小的。

JavaScript代码：

var sum_width_iterations = 0
var total_width_summed = 0

var sum_width_cache = {}

function sum_width(A, i, width){
  let key = `${i},${width}`
  
  if (sum_width_cache.hasOwnProperty(key))
    return sum_width_cache[key]
    
  sum_width_iterations++
  total_width_summed += width

  let result = 0
  for (let j=A.length-width; j<A.length; j++)
    result += ~~(A[j] / (j + 1 - i))
  return sum_width_cache[key] = result
}

function get_b(A){
  let result = []
  A.map(function(a, i){
    result.push(sum_width(A, i, A.length - i))
})
  return result
}

function find_s_greater_than_k(A, width, low, high, k){
  let mid = low + ((high - low) >> 1)
  let s = sum_width(A, mid, width)
  while (low <= high){
    mid = low + ((high - low) >> 1)
    s = sum_width(A, mid, width)
    if (s > k)
      high = mid - 1
    else
      low = mid + 1
  }
  return [mid, s]
}

function f(A, k, l, r){
  let n = A.length
  
  if (l > r){
  
console.log(`l > r: l, r: ${l}, ${r}`)
  
    return [n + 1, Infinity]
  }
  
  let width = n - l
  
console.log(`\n(call) width, l, r: ${width}, ${l}, ${r}`)

  let mid = l + ((r - l) >> 1)
  let mid_width = n - mid
  
console.log(`mid: ${mid}`)
console.log('mid_width: ' + mid_width)

  let highest_i = n - mid_width
  let [i, s] = find_s_greater_than_k(A, mid_width, 0, highest_i, k)

console.log(`hi_i, s,i,k: ${highest_i}, ${s}, ${i}, ${k}`)

  if (mid_width == width)
    return [i, s]

  // either way we need to look left
  // and down

console.log(`calling left`)

  let [li, ls] = f(A, k, l, mid - 1)

  // if i is the highest, width is
  // the width of b_i

console.log(`got left: li, ls, i, high_i: ${li}, ${ls}, ${i}, ${highest_i}`)

  if (i == highest_i){

console.log(`i == highest_i, s <= k: ${s <= k}`)

    // b_i is small enough
    if (s <= k){
      if (ls <= k)
        return [li, ls]
      else
        return [i, s]

    // b_i is larger than k
    } else {

console.log(`b_i > k`)

      let [ri, rs] = f(A, k, mid + 1, r)

console.log(`ri, rs: ${ri}, ${rs}`)

      if (ls <= k)
        return [li, ls]
      else if (rs <= k)
        return [ri, rs]
      else
        return [i, s]
    }
    
  // i < highest_i
  } else {

  console.log(`i < highest_i: high_i, i, s, li, ls, mid, mid_width, width, l, r: ${highest_i}, ${i}, ${s}, ${li}, ${ls}, ${mid}, ${mid_width}, ${width}, ${l}, ${r}`)
  
    // get the full sum for this b
    let b_i = sum_width(A, i, n - i)
      
console.log(`b_i: ${b_i}`)
  
    // suffix sum is less than k
    // so we cannot rule out either side
    if (s < k){
    
console.log(`s < k`)

      let ll = l
      let lr = mid - 1
      let [lli, lls] = f(A, k, ll, lr)
      
console.log(`ll, lr, lli, lls: ${ll}, ${lr}, ${lli}, ${lls}`)
      
      // b_i is a match so we don't
      // need to look to the right
      if (b_i <= k){
      
console.log(`b_i <= k: i, b_i: ${i}, ${b_i}`)
      
        if (lls <= k)
          return [lli, lls]
        else
          return [i, b_i]
      
      // b_i > k
      } else {
      
console.log(`b_i > k: i, b_i: ${i}, ${b_i}`)
      
        let rl = mid + 1
        let rr = r
        let [rri, rrs] = f(A, k, rl, rr)
      
console.log(`rl, rr, rri, rrs: ${rl}, ${rr}, ${rri}, ${rrs}`)
      
        // return the best of right
        // and left sections
        if (lls <= k)
          return [lli, lls]
        else if (rrs <= k)
          return [rri, rrs]
        else
          return [i, b_i]
      }
    
    // suffix sum is greater than or
    // equal to k so we can rule out
    // this and all higher rows (`b`s)
    // that share this suffix
    } else {
    
console.log(`s >= k`)

      let ll = l
      // the suffix rules out b_i
      // and above
      let lr = i - 1
      let [lli, lls] = f(A, k, ll, lr)
      
console.log(`ll, lr, lli, lls: ${ll}, ${lr}, ${lli}, ${lls}`)

      let rl = highest_i + 1
      let rr = r
      let [rri, rrs] = f(A, k, rl, rr)
      
console.log(`rl, rr, rri, rrs: ${rl}, ${rr}, ${rri}, ${rrs}`)

      // return the best of right
      // and left sections
      if (lls <= k)
        return [lli, lls]
      else if (rrs <= k)
        return [rri, rrs]
      else
        return [i, b_i]
    }
  }
}

let lst = [1, 2, 3, 1]
     // b [3, 3, 3, 1]
     
lst = [ 1, 34,  3,  2,  9, 21, 3, 2, 2, 1]
//  b [23, 41, 12, 13, 20, 22, 4, 3, 2, 1]

console.log(
  JSON.stringify(f(lst, 20, 0, lst.length)))

console.log(`sum_width_iterations: ${sum_width_iterations}`)

console.log(`total_width_summed: ${total_width_summed}`)

- גלעד ברקן

Answer 3

为什么计算b[i]会导致O(n²)的时间复杂度？如果i=1，则需要n步。如果i=n，则只需要一步计算b[i]...

当你在条件Sum > k下中止求和时，可以改进你的计算。

Let a in N^n
Let k in N

for (i1 := 1; i1 <= n; i1++)
  b := 0
  for (i2 :=i1; i2 <= n; i2++)   // This loop is the calculation of b[i]
    b := b + ceil(a[i2]/(i2 + 1))
    if (b > k)
      break
  if (i2 == n)
    return i1

- Sven-Eric Krüger

---

1+2+3+...+n = n(n+1)/2，这个式子的时间复杂度是O(n^2)。break语句可以减少平均运行时间，但不能改善最坏情况下的运行时间。因此，整个算法的时间复杂度仍然是O(n^2)。 - user3386109

该算法的时间复杂度是n的二次函数。第一步需要n个单位时间，第二步需要(n-1)个单位时间，第三步需要(n-2)个单位时间，以此类推。总共有n个步骤。因此，计算复杂度的上限为O(n²)。 - Reaz Murshed

如果 K 比输入值大得足够多，那么你的算法根本没有任何改进。因此，这不是问题的解决方案。 - Reaz Murshed