由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Minimum number of moves to make an integer array balance
相关主题
Google电话面试题目请教个面试题
C++ Q78: about sizeof问一道面试题目
[合集] Google电话面试题目问个最近面试里的题目
这题怎么做?一道老题
Given an array of N integers from range [0, N] and one is missing. Find the missing number.careercup上这道题我竟然没看懂
问道题,谁给个效率高点的解法算法题:两列找共同元素有O(n)的算法吗?
菜鸟问个two sum的变型题a[i] + b[j] = c[k] 的题有靠谱的答案不?
请教一道算法题amazon 电面问题 求解答, 在线等
相关话题的讨论汇总
话题: lo话题: 22话题: array话题: sum话题: up
进入JobHunting版参与讨论
1 (共1页)
f**********n
发帖数: 258
1
The problem is "Minimum number of moves to make an integer array balance".
Move is defined as reducing one element in array and increase anther integer
.
Balance is defined as the maximum difference between two integers in whole
array is 1.
lo=floor(average of array x)
up=ceil(average of array x)
lo_sum =the sum of all (lo - x[i]) for each x[i] up_sum=the sum of all (x[i]-up) for each x[i]>up
My solution is max(lo_sum, up_sum)
Here are several examples with my solution going through.
[1 2 3] with lo=up=2 max(2-x[0], x[2]-2)=1 correct
[4 1 3 2] with average=9/4=2 lo=2 up=3 max(2-x[1], x[0]-3)=1 correct
[5 100 2 0 3] output 78 to get [22 22 22 22]
with average=22 lo=up=22 max(22-5+22-2+22-0+22-3, 100-22)=78
[1 4 4 4 4 4 4] should output 2
with average=25/7=3 lo=3 up=4
max(3-1, 0)=2 also correct
请问这个解法有啥问题吗?
1 (共1页)
进入JobHunting版参与讨论
相关主题
amazon 电面问题 求解答, 在线等Given an array of N integers from range [0, N] and one is missing. Find the missing number.
求这道题的O(N)解 (转载)问道题,谁给个效率高点的解法
说说某著名软件公司的onsite面试菜鸟问个two sum的变型题
问几个老算法题的最佳解法请教一道算法题
Google电话面试题目请教个面试题
C++ Q78: about sizeof问一道面试题目
[合集] Google电话面试题目问个最近面试里的题目
这题怎么做?一道老题
相关话题的讨论汇总
话题: lo话题: 22话题: array话题: sum话题: up