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

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

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

剛好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;
}
}
}
}
  回復  更多評論
  

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;
}  回復  更多評論
  

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;
}
}
}   回復  更多評論
  

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

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

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

@ChenA

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

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

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

  回復  更多評論
  

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

最后一步我寫反了，暈。
遍歷數組,求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


  回復  更多評論
  

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

位圖。。。  回復  更多評論
  

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

+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;
}
  回復  更多評論
  

@Qiongzhu

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

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

}

呵呵。。。  回復  更多評論
  

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

+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，可以表示和，以及平方和

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

正解  回復  更多評論