由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 请教一个问题
相关主题
周末上道题search in a rotated array
求教一个onsite面试题目请教一个算法题
找最大、第二大元素问题找2个sorted array中的第K小的元素,有O(lgn)方法吗?
周末上道小题请教一个常见的面试题的答案
今天的一个面试题目binary search in rotated sorted array有重复时怎么办?
问个算法题One Amazon question
minimize the max of sums of each segment in an array问个rotated array里面找element的问题
算法--找一个unsorted array的largest and second largest 最请教一道题
相关话题的讨论汇总
话题: array话题: 相等话题: 元素话题: 操作话题: should
进入JobHunting版参与讨论
1 (共1页)
H****S
发帖数: 1359
1
有一个Array。一次操作定义为对于其中每一个元素加一或者减一 (每个元素既可以加
一也可以减一,不必都一样),问至少需要多少此这样的操作,可以让Array里面的数
都相等。如果不可能达到,输出-1.
r********7
发帖数: 32
2
从这个操作上可以看出,array中的两个数之间的差每次只会变化+2或者-2,而最终可
以两个数之间的差要变为0,所以如果通过这种操作能使array里面的数都相等,array
里面的数要么都是偶数要么都是奇数。
假设array里面的元素都是整数。
先考虑最简单的情况:
(1)array只有两个数,那么很容易验证:让array里面的元素都相等的操作次数应该
是(y-x)/2。
(2)array有两个以上的数,这个时候可以利用(1)中的结论,因为要使所有的元素
相等等价于使元素之间两两相等。比如现在有a[0] = x,a[1] = y,a[2] = z三个元素并
假设x 第一步:先让a[0]和a[1]相等,这个过程中a[2]进行与a[1]一样的操作,需要(y-x)/2
次操作,得到
a[0] = a[1] = (x+y)/2, a[2] = z-(y-x)/2
第二步:让a[0],a[1]与a[2]相等,需要(z-y)/2次操作,
最终得到
a[0] = a[1] = a[2] = (z+x)/2
两步一共需要(z-x)/2次操作。对于有3个以上元素的情况可以类推。
同时,这已经是最小的次数了,因为即使要让a[0]和a[2]相等,也需要(z-x)/2次。
所以最小次数应该是(最大值-最小值)/2。
H****S
发帖数: 1359
3
Bingo! This is a prefect answer:-) So in the process of transformation,
whenever we detected abs(a[i] - a[i + 1]) == 1, the program should
immediately output -1.

array

【在 r********7 的大作中提到】
: 从这个操作上可以看出,array中的两个数之间的差每次只会变化+2或者-2,而最终可
: 以两个数之间的差要变为0,所以如果通过这种操作能使array里面的数都相等,array
: 里面的数要么都是偶数要么都是奇数。
: 假设array里面的元素都是整数。
: 先考虑最简单的情况:
: (1)array只有两个数,那么很容易验证:让array里面的元素都相等的操作次数应该
: 是(y-x)/2。
: (2)array有两个以上的数,这个时候可以利用(1)中的结论,因为要使所有的元素
: 相等等价于使元素之间两两相等。比如现在有a[0] = x,a[1] = y,a[2] = z三个元素并
: 假设x
l*x
发帖数: 14021
4
Should be (a[i]+a[i+1])#2 '=0 which means the sum of these two number is odd
. This way, you can output -1 earlier.

【在 H****S 的大作中提到】
: Bingo! This is a prefect answer:-) So in the process of transformation,
: whenever we detected abs(a[i] - a[i + 1]) == 1, the program should
: immediately output -1.
:
: array

z****i
发帖数: 102
5
The final equal number needs to be equal to the average of all numbers.
Otherwise it is not minimum. The number of changes is the sum of abs(num-ave
).
1 (共1页)
进入JobHunting版参与讨论
相关主题
请教一道题今天的一个面试题目
如何找到第kth数 在32个sorted array问个算法题
M大小的数组中选出前N个元素 (如果M和N都很大)minimize the max of sums of each segment in an array
再论 mini # of swaps to sort array.算法--找一个unsorted array的largest and second largest 最
周末上道题search in a rotated array
求教一个onsite面试题目请教一个算法题
找最大、第二大元素问题找2个sorted array中的第K小的元素,有O(lgn)方法吗?
周末上道小题请教一个常见的面试题的答案
相关话题的讨论汇总
话题: array话题: 相等话题: 元素话题: 操作话题: should