posts - 3,  comments - 28,  trackbacks - 0
题目:

从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 猪头饼 阅读(3502) 评论(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 |
+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,可以表示和,以及平方和

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

正解  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2007年3月>
25262728123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

积分与排名

  • 积分 - 6785
  • 排名 - 1367

最新评论

阅读排行榜

评论排行榜