什麼是更快的算法來重新排列給定的數組數組

-1

問題是來自代碼鬥爭，其中指出：無限數量的框排列在一行中並從左到右編號。左邊的第一個盒子是第一個，下一個盒子是第二個，等等。n個球放在n個盒子中，每個盒子只能有一個球。你想組織球，所以你決定把所有的球排列在一起。他們應該佔用連續的一組盒子。您可以一球拿下一個球並將其移入空盒子中。什麼是更快的算法來重新排列給定的數組數組

給定一個指示放置球的盒子數量的數組球，找到組織球所需的最小數量的移動。

例

對於滾珠= [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中。

來源

2017-03-08 user1179317

什麼是這個當前算法大O複雜的代碼？ – Bobby

我建議你把它移到CodeReview.StackExchange.com; StackOverflow通常用於非工作代碼。 – Prune

欲獲得此處的幫助，請發佈長期運行的測試用例的驅動代碼。 – Prune

該代碼仔細計算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))

來源

2017-03-08 18:26:46

謝謝，這個有意義，效果很好 – user1179317

首先，你用範圍和設置結構燃燒了很多時間。退出檢查實際的球位置和空盒子。所有你需要的是移動的數量，而不是被移動的實際球。

例如，給定類似於[1,2,100,103,104,106,999,9999]的東西，你不在意什麼這四個異常值是什麼， 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

如果你有點固執的話，你可以將此減少到單行。

來源

2017-03-08 18:12:39 Prune

一個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;}

來源

2017-05-04 17:40:52 Archith

什麼是更快的算法來重新排列給定的數組數組

回答

相關問題