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

2021-03-04 00:54:17 +08:00
 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
1911 次点击
所在节点    程序员
12 条回复
also24
2021-03-04 01:09:54 +08:00
先遍历一遍,求个平均值 A (也就是目标值)

然后两个指针(下标)从头开始遍历,
little 指针找 <=a-1 的数,找到就停下来;
big 指针找 >= a+1 的数,找到就停下来;

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

注意,考虑到不能整除的情况,可以维护一个 SUM,每次切换新指针的时候,将已经无法处理的数字减去,求剩余可操作数字的新的平均值。
akira
2021-03-04 03:00:33 +08:00
没看懂。。你怎么移动,元素不还是那几个元素么,那不管你要什么结果,无非都是排序的事情吧
kx5d62Jn1J9MjoXP
2021-03-04 08:31:07 +08:00
要考虑平均值不为整数的情况,会有一点细节,但是还是可以做到 O(n)
woyixinyiyi
2021-03-04 09:45:05 +08:00
@also24
我之前也是这样想的
但是交换的时候 还有平均之外的值
然后 big -> little 完成一次交换,输出一次;
判断两个指针是否需要更新,继续输出一次。
woyixinyiyi
2021-03-04 09:45:37 +08:00
@akira 排序数组下标不就变了么
DeathBless
2021-03-04 09:45:52 +08:00
先算平均值 并用坐标排序

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

任意一端的值达到平均值就把指针往中间挪一个?
also24
2021-03-04 10:13:09 +08:00
@woyixinyiyi
没看懂你的回复,什么叫做 『还有平均之外的值』
siyemiaokube
2021-03-04 11:17:44 +08:00
直接按照题意模拟就行了,开两个列表

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

然后 L1 与 L2 最多存在一者,其中还存在既不为 ceil(avg)也不为 floor(avg)的数字,把这个数字继续摊平就行了。
siyemiaokube
2021-03-04 11:18:13 +08:00
把这个数字继续摊平就行了-> 把这些数字继续摊平就行了
bfdh
2021-03-08 08:56:36 +08:00
@also24 #7 应该说的是平均值不是整数的情况。如果平均值不是整数,应该要四舍五入之后做为目标值。
also24
2021-03-12 12:26:32 +08:00
@bfdh #10
不能直接四舍五入,直接四舍五入存在不均匀的情况。

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


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



这样,当指针移到最后两个位置的时候,平均值已经更新为 5 了,就能正确处理最后两个数字。
woyixinyiyi
2021-03-13 20:59:51 +08:00
@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++;

}
}
}

}

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/758227

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX