使数组的元素尽量平均的一道算法题

[woyixinyiyi]

想了半天没思路，请大佬赐教。

题目给任意一个数组 eg：int[] array = {1, 2, 3, 9, 5};

每次操作只能对某个数组下标对应的元素+1，另外的一个数组下标元素-1. 通过多次操作后，使各个元素的值尽量平均，（操作的次数尽量少，多也行，先实现功能再优化） 同时要求，输出每次移动的时候，是那个数组下标对应的元素加了还是减少了。

eg：9 移动了三次到 1 输出三次 3->0 (9 的下标是 3，1 的下标是 0)

9 移动了两次到 2
输出 2 此 3->1

[also24]

先遍历一遍，求个平均值 A （也就是目标值）

然后两个指针（下标）从头开始遍历，
little 指针找 <=a-1 的数，找到就停下来；
big 指针找 >= a+1 的数，找到就停下来；

然后 big -> little 完成一次交换，输出一次；
判断两个指针是否需要更新，继续输出一次。

注意，考虑到不能整除的情况，可以维护一个 SUM，每次切换新指针的时候，将已经无法处理的数字减去，求剩余可操作数字的新的平均值。

[akira]

没看懂。。你怎么移动，元素不还是那几个元素么，那不管你要什么结果，无非都是排序的事情吧

[kx5d62Jn1J9MjoXP]

要考虑平均值不为整数的情况，会有一点细节，但是还是可以做到 O(n)

[woyixinyiyi]

@also24
我之前也是这样想的
但是交换的时候 还有平均之外的值
然后 big -> little 完成一次交换，输出一次；
判断两个指针是否需要更新，继续输出一次。

[woyixinyiyi]

@akira 排序数组下标不就变了么

[DeathBless]

先算平均值 并用坐标排序

再用排序数组两头（一大 一小）的值做均衡

任意一端的值达到平均值就把指针往中间挪一个？

[also24]

@woyixinyiyi
没看懂你的回复，什么叫做 『还有平均之外的值』

[siyemiaokube]

直接按照题意模拟就行了，开两个列表

L1 储存大于 avg 的数，L2 储存小于 avg 的数字，先把 L1 尽可能地调整到 ceil(avg)，L2 尽可能调整到 floor(avg)。

然后 L1 与 L2 最多存在一者，其中还存在既不为 ceil(avg)也不为 floor(avg)的数字，把这个数字继续摊平就行了。

[siyemiaokube]

把这个数字继续摊平就行了-> 把这些数字继续摊平就行了

[bfdh]

@also24 #7 应该说的是平均值不是整数的情况。如果平均值不是整数，应该要四舍五入之后做为目标值。

[also24]

@bfdh #10
不能直接四舍五入，直接四舍五入存在不均匀的情况。

例如 4 4 4 3 7 这一组数字，平均值 4.4，四舍五入以后变成了 4，会导致处理到 3 的时候，误认为只需要增加到 4 就够了，实际上这个数列的最佳结果是 4 4 4 5 5 才对。


所以我在 1 楼的回答里，提到了平均值需要在每一次切换指针的时候进行更新：



这样，当指针移到最后两个位置的时候，平均值已经更新为 5 了，就能正确处理最后两个数字。

[woyixinyiyi]

@also24
谢谢老哥
实现了一版

public class 端盘子移动问题 {
/**
* 思路
* 1.计算出 平均值，四舍五入。这样会尽量的平均
* 2.维护两个指针，分别记录小于平均值的指针，和大于平均值的指针
* 3.然后移动大小指针来均值计算。
*/
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};

double sum = 0;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}

int avg = new BigDecimal(sum / array.length).setScale(0, BigDecimal.ROUND_HALF_UP).toBigInteger().intValue();

int small = 0;
int big = 0;

while (small < array.length && big < array.length) {


while (small < array.length && array[small] > avg) {
small++;
}

while (big < array.length && array[big] < avg) {
big++;
}

if (big >= array.length || small >= array.length) break;

//说明小于平均值的缺的盘子更多
if (Math.abs(array[small] - avg) > Math.abs(array[big] - avg)) {
int cha = Math.abs(array[big] - avg);
array[big] -= cha;
array[small] += cha;
big++;

} else {
int cha = Math.abs(array[small] - avg);
array[small] += cha;
array[big] -= cha;
small++;

}
}
}

}