[今日头条]面试题:int数组求平均数

sn-1*(n-1/n)+sn/n

维护两个变量，当前平均数，盈余，从1到n读数，每读一个数更新一次当前平均数和盈余，想象一下把新的数均摊到以前的数的样子

一面游

随便取数组中的1个数，比如数组中 50 49 73 89 71，取50。然后遍历数组中的数，并减去50，再相加，如 49 - 50 = -1，73 - 50 的23。把所有差值相加再除以数组长度，最后加上50就行了。。。。。。这样可以不

请问面了多久，还问了什么问题呀

先用数组模拟数字的相加，最后得到的数字用数组维护，然后用最后数组维护的数字除2就好了。比如1,2,3,4,5最后相加得到的是15，即a[2]={'1', '5'}，从高位1开始除2，商为0，余数为1，把余数乘10加到5的15,15除2，商为7，余数为1。最后没数可以除了，余数又不等于0，所以再加上0.5，即7.5。

这样不知道可行不？ public static int getAverage(int[] arrays) { int length = arrays.length; int average = 0; int r = 0; for (int i = 0; i < length; i++) { //累加整数部分平均数 average += arrays[i] / length; //余数部分处理 int curR = arrays[i] % length; if(r == 0){ r = curR; } else { //通过先去掉length，来解决相加溢出问题 int t = r > 0 ? r - length + curR : r + length + curR; if(Math.abs(t) > 0){ average = r > 0 ? average + 1 : average - 1; r=t; } else { r+=curR; } } } return average; }

归并了解一下

直接递归调用二路归并方法就能算

楼主思路是对的，但是写得复杂了，关键就是现有余数r和新的余数a[i] % N合并这步，可以直接判断相加后是否大于N，因为r和a[i] % N的范围都是左闭右开区间[0, N)，因此N-r和a[i] % N的范围也是[0, N)，比较大小即可。 int get_average(int a[], int n) { int aver = 0; int rest = 0; // [0, n) for (int i = 0; i < n; ++i) { aver += a[i] / n; int temp = a[i] % n; if (temp < 0) { temp += n; aver -= 1; } if (rest > n - temp) { // rest + temp > n，防止溢出 aver++; rest -= (n - temp); } else { rest += temp; } } return (aver >= 0) ? aver : aver + 1; // 假定负数结果向0取整 } 思路参考Quora上的问答，但是原***括楼主的做法都有一点没考虑到，那就是负数是否向0取整的问题。比如-25 / 9和-25 % 9的值，在C/C++/Java这种语言中，结果分别是-2和-7，而在中间处理时，合适的结果应该是-3和2，否则会出问题。比如楼主的程序对{-10, 3, 9}结果是1，对{-10, 3, 8}结果是0，对{-10, 3, 7}的结果是-1。原答案的程序对{-10, 3, 9}结果是1，对{-10, 3, 8}结果是0，对{-10, 3, 7}的结果是0。但如果最后结果需要负数向0取整的话，还要再判断结果是否为负数，若为负数，则需要加1。 另外，对于输入是数据流而非固定数组的情况，稍微就有点麻烦。设x(k)和r(k)依次是数组a[1..k]（为方便，下标从1开始）的平均值（取整）和余数。那么有 x(k+1) = (k * x(k) + r(k) + a[k+1]) / (k+1) = x(k) + (r(k) + a[k+1] - x(k)) / (k+1) r(k+1) = (r(k) + a[k+1] - x(k)) % (k+1) 关键就是在不溢出的情况下求(r(k) + a[k+1] - x(k)) / (k+1)，相当于求大小为3的数组{r(k), a[k+1], -x(k)}的加权平均值，不过权重不是1/3而是1/(k+1)。看似如此，实际上-x(k)可能溢出，因为INT_MAX的绝对值比INT_MIN的绝对值小1，所以x(k)是INT_MIN即0x80000000的时候，-x(k)仍然是0x80000000，溢出。至于数据流特别大，也就是说元素数量k超过了int的范围的话，考虑就更为复杂了。综上，这个问题其实……仔细想下其实没那么简单……不知道楼上说归并的是个什么思路……

用多个int模拟long 这种类型, sum = a * M + b 每次先加到b, 然后多出的话就b -= M, a++ ?