什么是更快的算法来重新排列给定的数组数组

-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

什么是更快的算法来重新排列给定的数组数组

回答

相关问题