与えられた配列の並び替えを高速化するアルゴリズムは何ですか

Question

問題は次のようなコードの戦いからです：無限の数のボックスが一列に並べられ、左から右に番号が付けられます。左側の最初のボックスは の番号1、次のボックスは2番の番号などです。n個のボールはボックスのn個に配置され、1個のボックスには1個のボールしか存在しません。 ボールを整理したいので、すべてのボールを隣り合わせに配置することにします。それらはボックスの連続したセットである を占有する必要があります。 1つのボールを取って、1つの移動で空のボックスに移動することができます。

ボールが配置されているボックスの番号を示す配列ボールが与えられている場合、ボールを整理するのに必要な最小移動数は です。

例

ボール= [6,4、1、7、10]の場合、出力は、この例で ballsRearranging（ボール）= 2

なければならない、移動の最小数は、必要に応じボール同士を隣り合わせに配置する方法は2です。ボックス1のボールは ボール5に、ボール10はボックス8（またはボックス3）に移動できます。

現在、私のコードは次のとおりです。

def ballsRearranging(balls): 
    ballsLength = len(balls) 
    partial = ballsLength//2 #INITIALLY SET TO HALF 
    setBalls = set(balls) 
    sortedBalls = sorted(balls) 
    minimum = 1000000 

    #####CHECK IF ITS ALREADY ORGANIZED 
    #####FIRST NUM PLUS LENGTH - 1 IS EQUAL TO THE LAST NUM 
    if sortedBalls[0]+ballsLength-1 == sortedBalls[-1]: 
     return 0 

    for i,num in enumerate(sortedBalls): 
     #####NO NEED TO GO PASS HALF WAY SINCE THAT AUTOMATICALLY MEANS HALF WILL BE OUT OF RANGE 
     #####THIS VALUE DYNAMICALLY CHANGES TO THE SMALLEST FRACTION OF OUT OF RANGE FOUND 
     if i >= partial: 
      break 

     #####IF WE TAKE THIS NUM AS THE BEGINNING, ORDERED BALLS WILL GO UP TO THE RANGE RNG 
     rng = range(num,num+ballsLength) 
     #####BALLS ALREADY IN THE RANGE RNG, WE WONT BE MOVING THESE BALLS 
     inRange = setBalls & set(rng) 

     #####BALLS NOT IN RANGE, EACH WILL BE REQUIRED TO MOVE 
     #####THE LENGTH OF THIS WILL BE THE NUMBER OF MOVES REQUIRED 
     outRange = setBalls - set(rng) 

     lenOutRange = len(outRange) 
     if lenOutRange < minimum: 
      minimum = lenOutRange 
      partial = 100*(lenOutRange/ballsLength) #UPDATE THE PARTIAL VALUE 

これはうまく動作しますが、現在はタイムアウトに隠されたテストで4Sの時間制限で。基本的に私のアルゴリズムは、指定された配列の最小の数から特定の部分（分数）になります。元のセットが与えられた範囲と交差する場所をチェックします。範囲外のアイテムが最も少ないものであれば、変更/再配置の最小回数になります。できればPythonでより良いアルゴリズムが何か不思議でした。

Answer 1

このコードは、O（n log n）時間の結果を計算するのに注意してください。ボールがすでにソートされている場合、これはO（n）の時間に実行されます。

これはキャタピラーアルゴリズムを使用します。ソートされたボールの配列にインデックスされた各jについて、iはインデックスjのボールのn-1の最初のボールを含むまで増分されます。これにより、j番目のボールで終わる範囲のボールの数を数えやすくなります。

def balls_rearranging(balls): 
    balls.sort() 
    best = 0 
    i = 0 
    for j in xrange(len(balls)): 
     while balls[i] <= balls[j] - len(balls): 
      i += 1 
     best = max(best, j - i + 1) 
    return len(balls) - best 

print balls_rearranging(range(0, 10000000, 2)) 

Answer 2

まず、あなたの範囲で多くの時間を費やしており、構造を設定しています。実際のボールの位置と空のボックスのチェックを終了します。必要なのは、移動される実際のボールではなく、移動量です。

たとえば、[1,2,100,103,104,106,9998,9999]のようなものを指定すると、あなたは気にしません何をこれら4つの外れ値は、 100の範囲。必要なのは量で、4

ソリューションは、シンプルなものに削減します。

size = len(balls) 
balls.sort() 
for box in balls: 
    # How many balls are in the range box : box+size-1 ? 
    # retain the maximum of these values 
return size - maximum # number of empty boxes in that range 

あなたはそれについて少し頑固であれば、あなたは、単一の行にこれを削減することができます。

Answer 3

ポール・ハンキンで貢献

コードのJavaバージョン

int ballsRearranging(int[] balls) { 
Arrays.sort(balls); // sort the array 
int i = 0; 
int j = 0; 
int max = 0; 
for(j = 0; j < balls.length;j++) { 
    while(balls[i] <= balls[j] - balls.length) { 
     i++; 
    } 
    max = Math.max(max,j-i+1); 
} 
return balls.length - max;}