是不是“微软最新面试题”本人没有考证：）
题目 见
http://community.csdn.net/Expert/TopicView3.asp?id=5337353
作 者： libihui422 (晶钻)
从1到1000000中任意拿掉两个数，把剩下的999998个数顺序打乱，并且放入数组中。要求只扫描一遍数组，把这两个数找出来。可以使用最到不超过5个局部变量，不能用数组变量，并且不能改变原数组的值。
思路 回复人：Oversense(步步文) ( 三级(初级)) 信誉：100 2007-2-4 1:04:56 得分:0
?
x+y=a
x*x+y*y=b
1+2-a[1]-a[2]+3+4-a[3]-a[4]
代码
#include
<
vector
>
#include
<
iostream
>
#include
<
algorithm
>
#include
<
iterator
>
#include
<
cstdio
>
using
namespace
std;#ifdef WIN32 typedef __int64 INT64; ostream
&
operator
<<
(ostream
&
os, INT64 n)
...
{ printf("%I64d", n); return os; }
#else
typedef unsigned
long
long
INT64; ostream
&
operator
<<
(ostream
&
os, INT64 n)
...
{ printf("%lld", n); return os; }
#endif
const
INT64 SIZE
=
1000001
;
void
init_array(vector
<
INT64
>&
array);
void
find_2_missing(
const
vector
<
INT64
>&
array);
int
main(
void
)
...
{ vector<INT64> array; init_array(array); find_2_missing(array); return 0;}
void
init_array(vector
<
INT64
>&
array)
...
{ array.resize(SIZE + 1); for (INT64 i = 0; i <= SIZE; ++i) ...{ array[i] = i; } cout << "input 2 missing numbers: "; int m1, m2; cin >> m1 >> m2; array[m1] = 0; array[m2] = 0;// copy(array.begin(), array.end(), ostream_iterator<INT64>(cout, " ")); random_shuffle(array.begin()+1, array.end());}
void
find_2_missing(
const
vector
<
INT64
>&
array)
...
{ INT64 x_plus_y = 0; INT64 xx_plus_yy = 0; for (INT64 i = 0; i <= SIZE; ++i) ...{ x_plus_y += i - array[i]; xx_plus_yy += i*i - array[i]*array[i]; } cout << "x + y = " << x_plus_y << endl; cout << "x^2 + y^2 = " << xx_plus_yy << endl;}
