3

たとえば、46、47、54、58、60、および 66 という数字があります。可能な限り最大のグループ サイズになるように、それらをグループ化したいと考えています。値がプラスまたはマイナス 10 (両端を含む) の範囲内にある場合、数値はグループ化されます。したがって、開始する数値に応じて、この例では 3 つの結果が考えられます (画像を参照)。

44 から 64 までの数字がグループ化され、66 だけが残り、最大のグループ (5 項目) が作成されるため、54 から始めた場合に発生する可能性のある 2 番目の結果が必要です。

この例では簡単にブルート フォースを実行できることはわかっていますが、実際には長い数のリストがあり、何千もの数にわたってこれを行う必要があります。読むべきアルゴリズムについて教えてくれたり、提案をくれたりできますか?

ここに画像の説明を入力

4

2 に答える 2

2

最初に配列を単純に並べ替えることができます。次に、i 番目の数値ごとにバイナリ検索を実行して、i 番目の数値 + 20 の範囲内にある最も右側の数値を見つけることができます。そのような最も右側のインデックスの位置を X とします。最大 (X-i+1) を見つける必要があります。すべての i 番目の数値について、これで完了です :)

実行時間分析: このアルゴリズムの実行時間は O(NlgN) です。ここで、N は元の配列の項目数です。

より良い解決策:配列 ar[] があり、ar[] に N 個の項目があると仮定しましょう。

  1. ar[] を非降順でソートする
  2. max_result = 0 に設定、cur_index = 0 に設定、i=0 に設定
  3. i を増やしながら i
  4. max_result を max(max_result,i-cur_index+1) に設定します
  5. 設定cur_index=cur_index+1
  6. もしcur_indexなら

ランタイム分析: O(N)、ここで N は配列 ar[] 内のアイテムの数です。

正しさ: 配列は非降順でソートされるため、if and i < jthenも。そのため、前の項目で既にチェックされているこれらの項目をチェックする必要はありません。j < kar[i]+20 > ar[k]ar[j]+20 > ar[k]

于 2013-08-07T17:17:53.437 に答える
0

これが私がやりたかったことです。申し訳ありませんが、私は自分自身をうまく説明していませんでした。各反復では、前の最大のグループを削除した後に残った数を使用して、可能な最大のグループを見つけます。Matlab コード:

function out=groupNums(y)
d=10;
out=[];
if length(y)==1
    out=y;
    return
end
group=[];
for i=1:length(y)
    group{i}=find(y<=y(i)+d & y>=y(i)-d);
end
[~,idx]=max(cellfun(@length,group));

out=[out,{y(group{idx})}];
y(group{idx})=[];
out=[out,groupNums(y)];
于 2013-08-07T17:50:31.960 に答える