注意题只能只扫描一遍数组:  回复  更多评论
  

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

结论：
只用到三个局部变量
循环中没有用到浮点数运算

正解  回复  更多评论