0

彼ら。

タイミングの良いアルゴがありますので、時間を良くするために変更する必要がありますが、わかりません。

手伝ってもらえますか？

時間は次のとおりです。

  • 実数0m0.164s
  • ユーザー0m0.021s
  • sys 0m0.010s

ここにアルゴがあります：

def algo2(A, B):
    x=0
    y=0
    for a in A:
          m=0
          for b in B:
                if a == b:
                      m += 1
          if m>y:
                x = a
                y = m
    return x;

algoの配列は次のとおりです
。A=[1,2,3,4,5,6,7,8,9,0]B = [1,2,3,4,5,6,4,7,8、 9,0]

4

1 に答える 1

0

アルゴリズムはO（n * m）です。配列が常にソートされている場合は、以下のように、ストレートマージ（O（n + m））を実行できます。（コードはPythonではないことに注意してください...アイデアを取得して翻訳できると思います）

ixA = 0
ixB = 0
maxVal = 0
maxCount = 0
workingVal = A[ixA]
workingCount = 0
while (ixA < A.length and ixB < B.length)
{
    if (workingVal == B[ixB])
    {
        workingCount += 1
    }
    else if (workingCount > maxCount)
    {
        maxCount = workingCount
        maxVal = workingVal
        workingCount = 0
        ixA += 1
        workingVal = A[ixA]
    }
    ixB += 1
}
// have to check the last one
if (workingCount > maxCount)
{
    maxCount = workingCount
    maxVal = workingVal
}

配列がソートされていない場合は、最初に配列をソートしてから、マージを実行できます。これは、O（m log m）+ O（n log n）+ O（m + n）になります。それでもあなたのO（m * n）よりはましです。

于 2013-03-25T14:04:27.827 に答える