问题描述

面试题，用最少的迭代，使数组所有元素变换为平均值（平衡）

输入：数组，所有值为非负整数
目标：通过变换使数组的每个值为所有值的平均值，并且迭代次数最少
变换方法：某个值自身减一，使其紧邻左边或紧邻右边的值加一。数组第一个值只能向右传递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实现。

解决方案

$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;
}

解决方案二：

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

解决方案三：

<?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: $numbern");
}
$averge=array_sum($argv)/($argc-1);
if(!is_int($averge)) exit("numbers you input,can not be balancen");
printArray($argv);
balance($argv,$averge);
?>

解决方案四：

我用了模仿例子的方法，无论自身大小，只要左右两边的值小于平均值就传递，显而易见的是有许多重复传递，谁还有其他方法吗，多谢
[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]

解决方案五：

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

解决方案六：

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

解决方案七：

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