1

找到总和可被 K 整除的最长子数组。在 O(n) 中可能吗？如果不能，那么 n^2 可以做得更好吗？

4

4 回答 4

8

让s[i] = sum of first i elements modulo K.

我们有：

s[i] = (s[i - 1] + a[i]) % K

我们必须为每个 找到i最小的j这样的s[i] == s[j]。您可以通过散列s[i]值来找到它。如果K很小，你可以只保留一个数组p[i] = first position for which s[k] == i。

复杂度是O(n)。

于 2012-10-26T14:53:01.747 回答
0 
function longestRangeDividableBy(k) {
  arrayOfRanges
  sum =0
  startIndex = 0
  endIndex = 0
  for ( i=0 ; i < array.size; i++) {
    sum += array[i]
    if (sum % k != 0) {
      endindex = i
    } else {
      arrayOfRanges.add(new Range(startIndex, endIndex);
      startIndex = i+1
      sum = 0
    }
  }
  arrayOfRanges.sortDescending();
  return arrayOfRanges.get(0).lengthOfRange()
}

这里我说范围的搜索是线性的。因此，它取决于算法是 O(n) 还是 n^2 的排序。如果我错了，请纠正我。

于 2012-10-26T14:52:46.420 回答
0

正如前面的答案所建议的，这可以在 O(N) 时间和空间内完成。其他答案提到了散列和排序。然而，这两个问题都不需要。在以下说明单次 O(N) 方法的 Python 程序中，rr是输入数组，vb[x]是第一个具有模值x的子和ve[x]的索引，是具有模值的最后一个子和的索引x。典型的输出显示在程序之后。

import random
K, N, vmax = 10, 25, 99
rr = [random.randrange(vmax) for x in range(N)]
print 'rr', rr
vb, ve = [-1 for x in range(K)],  [-1 for x in range(K)]
vb[0] = ve[0] = mb = me = ms = s = 0

for i in range(N):
    s = (s + rr[i]) % K
    ve[s] = i+1
    if vb[s] < 0:
        vb[s] = i+1
    if ve[s] - vb[s] > me - mb:
        mb, me, ms = vb[s], ve[s], s

print "Max len is", me-mb, "for rem", ms, "at [", mb,":",me, "], total=", sum(rr[mb:me])

典型输出，对于 K=10 和 N=25：

rr [26, 57, 0, 70, 33, 94, 23, 60, 62, 3, 28, 14, 12, 72, 6, 86, 29, 10, 60, 50, 21, 37, 40, 96, 73]
Max len is 21 for rem 3 at [ 2 : 23 ], total= 810
于 2012-10-26T19:31:27.120 回答
0 
    as rightly pointed out by @IVIad you have to keep a track of the current 
sum modulo k. 
you can write it as s=0
          s=(s+arr1[i])%k 
    after that in a for loop you can use a dictionary and see if the 
s is present in dictionary ; 
if yes then update the length else update the dictionary .
    below is the code.


    def longestsubsarraywithsumdivisiblebyk(arr1,k):
        h={}
        h[0]=-1
        maxlen=0
        s=0
        for i in range(len(arr1)):
            s=(s+arr1[i])%k
            if s in h:
                maxlen=max(maxlen,i-h[s])
            else:
                h[s]=i
        return maxlen
于 2018-11-05T06:02:28.467 回答