r**********a
发帖数: 1067 | 1 把从１到１０００的数字随机的顺序存入一个size为１０００的Array，如果拿走其中
一个数字，请找出哪个数字被换成了-1，并返回这个数字在Array中的index。
这个我做出来了， １到１０００的和 － Array中每个item的和 +１ = 那个数字。 然
后loop整个array找到-1所在的位置, 就是index。
又问：如果拿走其中两个数字，请找出哪两个数字被换成了-1，并返回这两个数字在
Array中的indexes。
请问这个怎么做？ |
j****i
发帖数: 305 | 2 Could you do S_n, and S_n^2?
【在 r**********a 的大作中提到】
: 把从１到１０００的数字随机的顺序存入一个size为１０００的Array，如果拿走其中
: 一个数字，请找出哪个数字被换成了-1，并返回这个数字在Array中的index。
: 这个我做出来了， １到１０００的和 － Array中每个item的和 +１ = 那个数字。 然
: 后loop整个array找到-1所在的位置, 就是index。
: 又问：如果拿走其中两个数字，请找出哪两个数字被换成了-1，并返回这两个数字在
: Array中的indexes。
: 请问这个怎么做？
|
r**********a
发帖数: 1067 | 3 不知道S＿n，S＿n＾２都代表什么， 能解释一下吗？
【在 j****i 的大作中提到】
: Could you do S_n, and S_n^2?
|
j****i
发帖数: 305 | 4 Straight sum, sum of squares.
【在 r**********a 的大作中提到】
: 不知道S＿n，S＿n＾２都代表什么， 能解释一下吗？
|
h**k
发帖数: 3368 | 5 另一种方法，
for i = 0 to 999
while a[i] != i && a[i] != -1
swap( a[i], a[a[i]] );
数字在
【在 r**********a 的大作中提到】
: 把从１到１０００的数字随机的顺序存入一个size为１０００的Array，如果拿走其中
: 一个数字，请找出哪个数字被换成了-1，并返回这个数字在Array中的index。
: 这个我做出来了， １到１０００的和 － Array中每个item的和 +１ = 那个数字。 然
: 后loop整个array找到-1所在的位置, 就是index。
: 又问：如果拿走其中两个数字，请找出哪两个数字被换成了-1，并返回这两个数字在
: Array中的indexes。
: 请问这个怎么做？
|
y*********e
发帖数: 518 | 6 假设只有1个数字X被替换掉了。那么新数组的和满足如下关系：
NEW_SUM = SUM + X - 1
SUM 是 1 + 2 + 3 + ... + 1000
NEW_SUM 就是把新数组遍历一遍，求和。
假设有2个数字，X和Y被替换掉了，那么新数组的和满足如下关系：
1. NEW_SUM = SUM + X + Y - 2
这里只有2个变量，一个方程，无法求解。需要建立另外一个方程，才能求解。
一个方法是求 SUM_OF_SQUARE，这样就可以建立起第二个方程：
2. NEW_SUM_SQUARE = SUM_SQUARE + X^2 + Y^2 - 2
方程1和方程2凑在一起，就可以求解出X和Y了。用掉O(n)的时间遍历，然后最后找出
index也要用掉O(n)的时间。
这个解法也适用于3个数被替换的情况。
如果数组没有重复的元素的话，另外一个解法可以用bitarray。用10bit来表示
1～1000的数字。若是某一个数字存在，就把该位的bit给set掉。
最后找没有set的bit，就直到哪个数被替换掉了。
数字在
【在 r**********a 的大作中提到】
: 把从１到１０００的数字随机的顺序存入一个size为１０００的Array，如果拿走其中
: 一个数字，请找出哪个数字被换成了-1，并返回这个数字在Array中的index。
: 这个我做出来了， １到１０００的和 － Array中每个item的和 +１ = 那个数字。 然
: 后loop整个array找到-1所在的位置, 就是index。
: 又问：如果拿走其中两个数字，请找出哪两个数字被换成了-1，并返回这两个数字在
: Array中的indexes。
: 请问这个怎么做？
|
n******0
发帖数: 61 | 7 I don't get the point, is this program related or not? Does the sum cost
more cpu time? |
