題目：

從1到N(100000)中任意拿掉兩個數，把剩下的99998個數順序打亂，并且放入數組A中。要求只掃描一遍數組，把這兩個數找出來?？梢允褂米畹讲怀^5個局部變量，不能用數組變量，并且不能改變原數組的值。

思路：

遍歷一次數組，求出這兩個數的和a+b 與積a*b
a+b = 1+2+3+4+...+N- sum(A[]);??? (1)
a*b =? 1*2*3*4*...*N / multi(A[]);?? (2)

主要解決sum與multi的溢出問題

(1) 可化為 (N-A[0]) + (N-1-A[1]) + ...+ (3-A[N-3]) + 2 + 1

(2) 可以用對數來代替原數進行求積的等價運算,避免溢出的問題，但是這種方法會產生一些精度上的問題，不知道大家有什么更好的方法！
先求出log(a*b)?:
?????????????????????????= log(1*2*3*4*....*N)/log(A[0]*A[1]*A[2]*...*A[N-3])
?????????????????????????= log(N)-log(A[0]) + log(N-1)-log(A[1]) + ... +log(3)-log(A[N-3]) + log(2) + log(1)
?????????
知道了兩數的和與積,由此就可以計算出a跟b的值來.

代碼如下：

#include?<iostream>

#include?<Ctime>

#include?<Cmath>

using?namespace?std;

#define?N?100000

//生成不同的隨機數的數組

void?GetDiffRandomNum(int?A[],?int?n)

{

????srand(unsigned(time(NULL)));

????int?i=0;

????for(int?index?=?n-1;?index?>?0;?index--)

????{

????????i?=?rand()?%?index;

????????swap(A[i],?A[index]);

????}

}

int?main()

{

????int?A[N]={0};

????for(int?i=0;?i<N;?i++)

????{

????????A[i]?=?i+1;

????}

????GetDiffRandomNum(A,?N);

????//DISPLAY(A,?N);

????

????unsigned?int?sum?=?0;

????double?logSum?=?0;

????for(i=0;?i<N-2;?i++)

????{

????????sum?+=?N-i-A[i];?????????????

????????logSum?+=?log(N-i)-log(A[i]);

????}

????sum?+=?2?+?1;

????logSum?+=?log(2)+log(1);

????double?multi?=?exp(logSum);

????//兩數的和與積

????cout<<int(sum)<<'\t'<<int(multi)<<endl;

????//求出兩數

????for(i=1;?i<=N;?i++)

????{

????????double?temp?=?i*(sum-i);

????????if(multi-0.5<=temp?&&?temp?<=?multi+0.5)

????????????cout<<i<<'\t'<<int(sum-i)<<endl;

????}

????return?0;

}

PS（謝謝枝~的幫助）請大家指導

//................................
通過大家的幫助：
得到另一個寫法，不會產生精度問題

(1+N)*N /2 - S = a + b
1/6 * n*(n + 1)*(2n + 1) - X = a*a + b*b

注：
1/6 * n*(n + 1)*(2n + 1)=1*1 + 2*2 + 3*3 +...+N*N
X = A[0]*A[0] + A[1]*A[1] +...A[N-3]*A[N-3]
?
==>
a + b = m
a*a + b*b = n

由于可解出a,b

????unsigned?int?sum?=?0;
????unsigned?int?sqrSum?=?0;

????for(i=0;?i<N-2;?i++)
????{
????????sum?+=?N-i-A[i];???????
????????sqrSum?+=?((N-i)*(N-i))?-?((A[i])*A[i]);
?????
????}
????sum?+=?2?+?1;?
????sqrSum?+=?2*2?+?1*1;

posted on 2007-03-22 23:14 豬頭餅閱讀(3719) 評論(18) 編輯收藏引用所屬分類: 算法/數據結構

FeedBack:

# re: 一道算法面試題，大家討論看看

2007-03-23 08:25 | OOKK

注意題只能只掃描一遍數組: 回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-23 08:47 | 萬連文

用5個變量記錄5位數字出現的次數，我想這樣，不知對否

筆試真tmd的米意思回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-23 08:50 | OOKK

剛好5個局部變量,剛好對A只掃描了一遍.還可以有更好的做法只需要一個循環就完成
void Func(int A[N-2], int &a, int &b)
{
set<int> oSet;
for(int i=0; i<(N-2); ++i)
oSet.insert(A[i]);
set<int>::iterator idx = oSet.begin();
if(idx == oSet.end())
{
a = 1;
b = 2;
}
else
{
int nCount = 0;
if(1 != *idx)
{
a = 1;
++nCount;
}
if( N != *oSet.rbegin())
{
b = N;
++nCount;
}
if(nCount != 2)
{
set<int>::iterator it = idx;
for(++it; it!=end; ++it, ++idx)
{
switch(*it - *idx)
{
case 2:
if(nCount)
b = *idx+1;
else
a = *idx+1;
++nCount;
break;
case 3:
a = *idx+1;
b = a + 1;
nCount = 2;
break;
}
if(nCount == 2)
break;
}
}
}
}
回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-23 09:03 | OOKK

void Func(int A[N-2], int &a, int &b)
{
set<int> oSet;
int i, nCount = 0;
for(int i=0; i<N; ++i)
oSet.insert(i+1);
for(int i=0; i<(N-2); ++i)
{
if(oSet.find(A[i]) != oSet.end())
oSet.erase(A[i]);
}
set<int>::iterator idx = oSet.begin();
a = *idx;
++idx;
b = *idx;
} 回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-23 09:09 | OOKK

void Func(int A[N-2], int &a, int &b)
{
int nCount = 0;
set<int> oSet(A, A+N-3);
for(int i=0; i<N; ++i)
{
if(oSet.find(i+1) == oSet.end())
{
if(nCount)
b = i+1;
else
a = i+1;
++nCount;
if(nCount == 2)
break;
}
}
} 回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-23 11:02 | david

set這種類型的變量應該不能用吧回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-23 11:50 | ChenA

不知道這個只遍歷一次是什么意思，你求sum(A[])不就遍歷了一次？

假設這兩個抽出來的數叫a，b，且a<b。
因為a!=b，那么a<(a+b)/2。
遍歷數組求小于(A+B)/2的A[i]的和，再減去0到i的和就得到了a。回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-23 12:58 | shen126

@ChenA

看不懂啊，能不能再明確一點？
假設只有三個數1,2,3;拿掉1,2;然后。。。？回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-23 20:48 | 豬頭餅

@OOKK
你第一個發布是代碼的思路能簡單的說說嗎？

@ChenA
是啊，我就遍歷了一次數組，求和與積啊。沒有違反規定啊
你說的那個方法能講的再詳細些么？

回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-24 10:06 | zeeng

太妙了，I　LIKE　IT. 回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-25 16:24 | ChenA

最后一步我寫反了，暈。
遍歷數組,求A中小于(a+b)/2的元素的和c，用1到<(a+b)/2的最大整數的和減去c就得到了a。

12345拿掉24
那么a+b =(1+5)*2.5-(1+3+5)=6;
那么a<3
遍歷數組(1,3,5)
所有小于3的數的和c=1
那么a=(1+2)-c=2
b=4

回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-27 11:06 | aaron

ChenA, 題目中 “把剩下的99998個數順序打亂，并且放入數組A中”，你這樣是按排好序的，不太對吧回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-27 15:39 | rome

位圖。。。回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-28 11:26 | Qiongzhu

To 豬頭餅:
1到100000之間平方和約有51位2進制位, 使用unsigned int在通常的32位機器上計算過程中會溢出. 應該使用編譯器的擴展長整型, 比如VC的 __int64, 也即 long long 型. 回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-28 14:37 | BearBlog

+1 Qiongzhu

思路：

遍歷一次數組，求出這兩個數的和a+b 與平方和a*a+b*b
a+b = 1+2+3+4+...+N- sum(A[]); (1)
a*a+b*b = (1*1)+(2*2)+(3*3)+(4*4)+...+(N*N) / sum(A[]*A[]); (2)

假設
m=a+b
n=a*a+b*b
則
a=(m+sqrt((2*n-m*m)))/2
b=(m-sqrt((2*n-m*m)))/2

邊界
N < pow(2, 17)
N*N < pow(2, 34) < pow(2, 63)
1+2+3+4+...+N的值為N*(N+1)/2 < pow(2, 33) < pow(2, 63)
(1*1)+(2*2)+(3*3)+(4*4)+...+(N*N) < N*N*N < pow(2, 50) < pow(2, 63)
使用編譯器的擴展長整型__int64，可以表示和，以及平方和

結論：
只用到三個局部變量
循環中沒有用到浮點數運算

代碼
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
#include <iostream>
#include <Ctime>
#include <Cmath>
using namespace std;

#define N 100000

//生成不同的隨機數的數組
void GetDiffRandomNum(int A[], int n)
{
srand(unsigned(time(NULL)));
int i=0;

for(int index = n-1; index > 0; index--)
{
i = rand() % index;
swap(A[i], A[index]);
}
}

// 把這兩個數找出來
void FindOutTwoNumbers(int A[], int nloss2)
{
// 局部變量
__int64 m = 0; // 和 10^5^2
__int64 n = 0; // 平方和 10^5^3
int i;

for (i = 0; i < nloss2; i++)
{
m += (i + 1) - A[i];
n += (i + 1) * (i + 1);
n -= A[i] * A[i];
}
m += (nloss2 + 1) + (nloss2 + 2);
n += (nloss2 + 1) * (nloss2 + 1);
n += (nloss2 + 2) * (nloss2 + 2);

cout<<m<<'\t'<<n<<endl;

cout<<(m+sqrt((double)(2*n-m*m)))/2<<'\t'<<(m-sqrt((double)(2*n-m*m)))/2<<endl;
}

int main()
{
int A[N]={0};
for(int i=0; i<N; i++)
{
A[i] = i+1;
}
GetDiffRandomNum(A, N);

// 抽掉最后兩個數
cout<<A[N-2]<<'\t'<<A[N-1]<<endl;

FindOutTwoNumbers(A, N-2);

return 0;
}
回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-28 18:58 | 豬頭餅

@Qiongzhu

32位是會溢出，所以我寫成這樣：

for(i=0; i<N-2; i++)
{
sum += N-i-A[i];
sqrSum += ((N-i)*(N-i)) - ((A[i])*A[i]); //

}

呵呵。。。回復更多評論

# re: 一道算法面試題，大家討論看看

2007-03-30 17:18 | 塌塌方

cout<<(m+sqrt((double)(2*n-m*m)))/2<<'\t'<<(m-sqrt((double)(2*n-m*m)))/2<<endl;
不知道有問題嗎回復更多評論

# re: 一道算法面試題，大家討論看看[未登錄]

2010-12-04 14:32 | 湯

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 一道算法面試題，大家討論看看 KMP算法資料

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2007年3月

日

一

二

三

四

五

六

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

積分與排名

積分 - 7286
排名 - 1354

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜