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最小のものを見つける必要があります。これは、値をハッシュすることで見つけることができます。が小さい場合は、配列を保持できます。js[i] == s[j]s[i]Kp[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）の時間と空間で実行できます。それらの他の答えは、ハッシュとソートに言及しています。ただし、この問題にはどちらも必要ありません。次のPythonプログラムでは、ワンパスO（N）メソッドを示し、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 に答える