2 shangguokan shangguokan 于 2014.12.13 03:51 提问

面试题,用最少的迭代,使数组所有元素变换为平均值(平衡)

输入:数组,所有值为非负整数
目标:通过变换使数组的每个值为所有值的平均值,并且迭代次数最少
变换方法:某个值自身减一,使其紧邻左边或紧邻右边的值加一。数组第一个值只能向右传递1,最后一个向左传递1. 变换过程中数组内所有值不可为负。
例1:
输入 : [0, 3, 3]
第一次: [1, 2, 3] [1, 3, 2]
第二次: [2, 2, 2]
例2
[2, 4, 6, 2, 1]
[3, 3, 5, 2, 2]
[3, 3, 4, 2, 3]
[3, 3, 3, 3, 3]
例3
[1, 0, 7, 0]
[1, 1, 6, 0]
[2, 1, 5, 0]
[2, 2, 4, 0]
[2, 2, 3, 1]
[2, 2, 2, 2]
这个问题有什么好的算法解决吗,例子不是唯一解。求思路,用php实现。

7个回答

xuzuning
xuzuning   Ds   Rxr 2014.12.13 10:44
已采纳
$ar = [0, 3, 3];
$ar = [2, 4, 6, 2, 1];
$ar = [1, 0, 7, 0];
$ar = [5, 5, 5, 5, 25];

do {
  $loop = 0;
  for($i=0; $i<count($ar) - 1; $i++) {
    if($n = casecmp($ar[$i], $ar[$i+1])) {
      $ar[$i] += $n;
      $ar[$i+1] -= $n;
      $loop++;
    }
  }
  printf("[%s]\n", join(', ', $ar));
}while($loop);

function casecmp($a, $b) {
  if($a == $b) return 0;
  return $a > $b ? -1 : 1;
}

xuzuning
xuzuning 回复shangguokan: 对呀,如果是0就不-1了,你总得判断一下吧?
大约 3 年之前 回复
shangguokan
shangguokan 回复xuzuning: 变换过程中所有值不可为负,指的是数组里如果有0,就不能再向外传递,然后变成-1了
大约 3 年之前 回复
xuzuning
xuzuning 回复shangguokan: 笑话,不能判别值,怎么保证:变换过程中所有值不可为负?
大约 3 年之前 回复
shangguokan
shangguokan Cool! thanks,对比也是一种思路啊,不过题目要求当前值只能向外传递,而不能取得值,只能减1,不能加1。 这里:$ar[$i] += (1/-1);
大约 3 年之前 回复
caozhy
caozhy   Ds   Rxr 2014.12.13 07:10

[1, 1, 6, 0]
[2, 1, 5, 0]
这是怎么来的,某个值自身减一,使其左边或右边的值加一,6减少1怎么加到第一个去的?

shangguokan
shangguokan 回复shangguokan: 所以重点是向左传还是向右传,传递规则以及怎样才能最快
大约 3 年之前 回复
shangguokan
shangguokan 一次遍历中 [1, 1, 6, 0] [2, 0, 6, 0] [2, 1, 5, 0] 这样来的, 即便第二个值为1小于平均值,还是向左传递了
大约 3 年之前 回复
shangguokan
shangguokan   2014.12.13 09:11
<?php 
function printArray($array){
    print "[";
    foreach ($array as $key => $value)
        $key==count($array)-1? print $value :print $value.", ";
    print "]\n";
}
function balance($a,$averge){
    while (1){
        $count=0;
    foreach ($a as $key => $value){
        $key==0?$left=null:$left=$a[$key-1];
        $key==count($a)-1?$right=null:$right=$a[$key+1];
        $value=$a[$key];
        if (is_null($left)&&$value>$averge) { $a[$key]--; $a[$key+1]++; continue;}
        if (is_null($right)&&$value>$averge) { $a[$key]--; $a[$key-1]++; continue;}
        if (!is_null($left)&&!is_null($right)&&$left<$averge&&$value!=0) { $a[$key]--; $a[$key-1]++;continue;}
        if (!is_null($left)&&!is_null($right)&&$right<$averge&&$value!=0) { $a[$key]--; $a[$key+1]++;continue;}
        $count++;
        if($count==count($a)) return 0;
    }
    printArray($a);
    }
}

if($argc<2) exit("php solution.php number1 number2 number3 ...\n");
array_shift($argv);
foreach ($argv as $number){
    if(!preg_match("/^[1-9]\d*$|^0$/",$number))
        exit("wrong number: $number\n");    
}
$averge=array_sum($argv)/($argc-1);
if(!is_int($averge)) exit("numbers you input,can not be balance\n");
printArray($argv);
balance($argv,$averge);
?>

shangguokan
shangguokan 对于例子[0, 10, 0, 10, 0],程序会卡在[4, 6, 4, 3, 3]上 6不传递(左右都是平均数) 4传给3后又传回去了
大约 3 年之前 回复
shangguokan
shangguokan   2014.12.13 09:26

我用了模仿例子的方法,无论自身大小,只要左右两边的值小于平均值就传递,显而易见的是有许多重复传递,谁还有其他方法吗,多谢
[5, 5, 5, 5, 25]
[6, 5, 5, 5, 24] //除了第一个值,所有值都向左传递了1
[7, 5, 5, 5, 23]
[8, 5, 5, 5, 22]
[9, 5, 5, 5, 21]// [9, 5, 5, 5, 21] [9, 4, 6, 5, 21] [9, 5, 5, 5, 21] [9, 5, 6, 4, 21] [9, 5, 6, 5, 20] 冗余
[9, 5, 6, 5, 20]
[9, 5, 7, 5, 19]
[9, 5, 8, 5, 18]
[9, 5, 9, 5, 17]
[9, 6, 9, 5, 16]
[9, 7, 9, 5, 15]
[9, 8, 9, 5, 14]
[9, 9, 9, 5, 13]
[9, 9, 9, 6, 12]
[9, 9, 9, 7, 11]
[9, 9, 9, 8, 10]
[9, 9, 9, 9, 9]

xianfajushi
xianfajushi   2014.12.13 09:41

如果从更广范围论,之上概念让人雾蒙蒙的,比如说一个较大的数字向左右如果跨多个位置如何得知?是否要循环检测其位置?如果要循环得到那么真的会比现有函数更高效?现有求数组平均值函数及数组生成重复值函数难道效率不行?

xianfajushi
xianfajushi   2014.12.13 09:54

减少迭代其实有些自欺欺人,比如用很多判断语句执行,其实处理器还是要操作,并不比直接迭代更高效?
比如循环一遍数组求得其均值再一遍赋值,这样语句精简适用更广

zefengyuan1989
zefengyuan1989   2015.06.14 23:55

求出均值,然后从数组首尾两段比较可以嘛?

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!