線形時間で与えられたkに対して少なくとも1回、すべての要素1〜kを含む最小の部分配列を見つける方法

Question

配列が{2 4 2 1 5 3 5 3}かつk = 3であると仮定します。 サブアレイ{2 1 5 3}には1 2 3が含まれています。

この問題を解決するための線形時間アルゴリズムがあるかどうかを知りたいと思います。

Answer 1

はい、あります：あなたは新しい間隔を見つけるたび

begin = -1 
end = -1 
best = 0 
new = 1 
finalbegin = -1 
finalend = -1 
for i = 1 to n 
    if (new and input[i] >= 1 and input <= k) 
     begin = i 
     new = 0 
    end if 
    if (new and (input[i] <= 1 or input[i] >= k) or (i = n)) 
     if (input[i] <= 1 or input[i] >= k) 
      end = i - 1 
     else 
      end = i 
     end if 
     new = 1 
     if (end - begin >= best) 
      finalbegin = begin 
      finalend = end 
      best = end - begin + 1 
     end if 
    end if 
end for 

は、あなたはそれがすでに発見された最良よりも優れているかどうかを確認してください。もしそうなら、あなたはそれを新しいベストとして扱います。 beginとendが負の場合、空集合が解です。そうでなければ、最も良い解決策は解決策です。