将整数x全部分配给数组元素使两两差值最小的最快实现方法

核心思路 #

我们的目标是把整数x全部分配到数组元素中，让最终数组的最大和最小元素差值尽可能小，本质是优先给更小的元素补数值，先把所有元素尽可能拉平，剩余的增量再均匀分配即可。

具体实现步骤 #

• 第一步：先把原数组从小到大排序，方便优先给数值小的元素补值
• 第二步：从左到右依次判断是否能把当前位置之前的所有元素都补到和下一个元素相等：
  以示例arr = [4,2,0]、x = 10为例，排序后数组为[0,2,4]
  第一个元素是0，下一个元素是2，补平前1个元素需要的增量是(2-0)*1=2，x足够扣除，x变为10-2=8，此时前1个元素均变为2，和第二个元素齐平
  接下来前2个元素都是2，下一个元素是4，补平需要的增量是(4-2)*2=4，x足够扣除，x变为8-4=4，此时前3个元素都变为4
• 第三步：所有元素已经齐平，剩下的x=4均匀分给3个元素，每个先分4//3=1，剩下4%3=1个增量给前1个元素额外加1
• 第四步：最终得到的数组就是[4+1+1,4+1,4+1] = [6,5,5]，和示例结果完全一致

可直接运行的Python代码 #

def distribute_x(arr, x):
    n = len(arr)
    # 记录原索引，最后还原数组原本的顺序
    sorted_arr = sorted([(val, idx) for idx, val in enumerate(arr)], key=lambda x: x[0])
    sorted_vals = [v for v, idx in sorted_arr]
    
    i = 0
    while i < n - 1 and x > 0:
        # 计算把前i+1个元素补到下一个元素的值需要的总增量
        diff = sorted_vals[i+1] - sorted_vals[i]
        required = diff * (i + 1)
        if x >= required:
            x -= required
            # 前i+1个元素都升到下一个元素的数值
            for j in range(i+1):
                sorted_vals[j] = sorted_vals[i+1]
            i += 1
        else:
            break
    # 剩余x均匀分配给所有元素
    add = x // n
    rem = x % n
    for j in range(n):
        sorted_vals[j] += add
    # 余数分给最前面的rem个元素，每个多补1
    for j in range(rem):
        sorted_vals[j] += 1
    
    # 还原为原数组的顺序
    res = [0] * n
    for idx in range(n):
        original_idx = sorted_arr[idx][1]
        res[original_idx] = sorted_vals[idx]
    return res

# 测试示例
print(distribute_x([4,2,0], 10)) # 输出 [6,5,5]

效果说明 #

这个方案可以保证最终数组任意两个元素的差值最大为1，是理论上能达到的最小差值，同时可以保证刚好用完所有x。

内容的提问来源于stack exchange，提问作者mohit kumar