今天腾讯笔试的一道题目，大家表达下自己的想法

int_i_j_k 2012-04-07 05:47:11

原题大概是：
两个数组a[N]，b[N]，其中A[N]的各个元素值已知，现给b[i]赋值，b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]；
要求：
1.不准用除法运算
2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等）
3.满足时间复杂度O（n），空间复杂度O（1）

...全文

5490 144 打赏收藏转发到动态举报

写回复

用AI写文章

144 条回复

切换为时间正序

请发表友善的回复…

发表回复

chongqingbear 2012-07-07

打赏
举报

都是大牛，高手在民间

int_i_j_k 2012-04-15

打赏
举报

是不是可以结贴了？回复貌似太多了...

bainaohdu 2012-04-13

打赏
举报

大家都很牛啊

龙战于野1988 2012-04-13

打赏
举报

20楼威武！

品茶 2012-04-13

打赏
举报

明白了
分成a[0]~a[i-1]和a[i+1]~a[N-1]两部分
代码不错收藏了

NovalIDE 2012-04-12

打赏
举报

[Quote=引用 131 楼的回复:]
引用 127 楼的回复:

上面的代码我测试过，没问题
不认真看题的哥们伤不起，还优化……
[/Quote]

请问我哪里错了。

lpy2604080318 2012-04-12

打赏
举报

我也晕

xxx_abbc_zz 2012-04-12

打赏
举报

分两个循环。左右遍历、

孤独小剑 2012-04-12

打赏
举报

[Quote=引用 127 楼的回复:]

上面的代码我测试过，没问题
[/Quote]不认真看题的哥们伤不起，还优化……

NovalIDE 2012-04-12

打赏
举报

for (int i = 0 ;i<N;i++){
b[i] = 1;
for (int j = 0 ;j < N;j++){
if (j == i){
continue;
}
b[i] *=a[j];
}
}

for (int i = 0 ;i<N;i++)
{
cout << b[i] <<endl;
}
优化后更简洁的代码

forevergg 2012-04-12

打赏
举报

哇擦，太犀利了。

孤独小剑 2012-04-12

打赏
举报

[Quote=引用 136 楼的回复:]

引用 135 楼的回复:
引用 134 楼的回复:

引用 131 楼的回复:
引用 127 楼的回复:

上面的代码我测试过，没问题
不认真看题的哥们伤不起，还优化……

请问我哪里错了。

引用 130 楼的回复:

for (int i = 0 ;i<N;i++){
b[i] = 1;
for (int j = 0 ;j < N;j++){……
[/Quote]1、腾讯原题和楼主描述的有点不一样，原题意思是：除一个迭代变量外不允许再申请任何多余的变量。即所有的信息为，数组a、b以及数组长度N，然后一个迭代变量i，其它再没有变量条件可用。按照要求做出来。
2、复杂度：你的复杂度是O(n^2)，题目要求O(n)

NovalIDE 2012-04-12

打赏
举报

[Quote=引用 135 楼的回复:]
引用 134 楼的回复:

引用 131 楼的回复:
引用 127 楼的回复:

上面的代码我测试过，没问题
不认真看题的哥们伤不起，还优化……

请问我哪里错了。

引用 130 楼的回复:

for (int i = 0 ;i<N;i++){
b[i] = 1;
for (int j = 0 ;j < N;j++){
if (j == i){
c……
[/Quote]

题目中的第二个要求，请仔细看
2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等）

i,j是循环中的计数值，是符合第二条的。
这个题，用循环的必须的，还没想到不用循环能解决的。
题目也要求用循环

孤独小剑 2012-04-12

打赏
举报

[Quote=引用 134 楼的回复:]

引用 131 楼的回复:
引用 127 楼的回复:

上面的代码我测试过，没问题
不认真看题的哥们伤不起，还优化……

请问我哪里错了。
[/Quote][Quote=引用 130 楼的回复:]

for (int i = 0 ;i<N;i++){
b[i] = 1;
for (int j = 0 ;j < N;j++){
if (j == i){
continue;
}
b[i] *=a[j];
}
}

for (int i = 0 ;i<N;i++)
{
cout << b[i] <<endl;
}
优化后更简洁的代码
[/Quote]1、题目要求时间复杂度O(n)你嵌套了for循环
2、要求只能使用一个迭代变量，不能使用其它任何形式的变量，你这里的i和j……

vivi_wang_11 2012-04-11

打赏
举报

[Quote=引用 69 楼的回复:]

引用 64 楼的回复:

b[0]=1;
for(int i=1;i<=N-1;i++)
{
b[i]=a[i-1]*b[i-1];
}
for(int i=N-1;i>0;i--)
{
b[i]=b[i]*b[0];
b[0]=b[0]*a[i];
}

这样呢
这个不错，可靠解决了b[0]等于b[0]的平方的尴尬。
[/Quote]

求第二题的题目和解法~~大家讨论下吧~~

vivi_wang_11 2012-04-11

打赏
举报

[Quote=引用 67 楼的回复:]

引用 56 楼的回复:

引用 20 楼的回复:

b[0] = 1;
for (int i = 1; i < N; i++)
{
b[0] *= a[i-1];
b[i] = b[0];
}

求第二题题目和解法啊~~~
b[0] = 1;
for (i = N-2; i > 0; i--)
{
b[0] *= a[i+1];
b[i] *= b[0];
}
b[0] *= a[1]……
[/Quote]

笨鸟明明 2012-04-11

打赏
举报

高手果然在人间

vivi_wang_11 2012-04-11

打赏
举报

[Quote=引用 6 楼的回复:]

不如讨论下第二道附加题吧。。。。还有意思点
[/Quote]

求题目~~想看看高端公司的高端题~~

abner_86 2012-04-11

打赏
举报

受不了这样的

NovalIDE 2012-04-11

打赏
举报

int _tmain(int argc, _TCHAR* argv[])
{
int N = 10;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
int b[10];
for (int i = 0 ;i<N;i++)
{
b[i] = 1;
for (int j = 0 ;j <= i-1;j++)
{
b[i] *=a[j];
}

for (int j = i+1 ;j < N;j++)
{
b[i] *= a[j];
}
}

for (int i = 0 ;i<N;i++)
{
cout << b[i] <<endl;
}
return 0;
}
优化了一下