搜狗笔试题，求教

一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素，即a[0]变为a[1]到a[n-1]的积
a[1]变为a[0]和a[2]到a[n-1]的积，...，a[n-1]为a[0]到a[n-2]的积。
程序要求：
要求具有线性复杂度。
不能使用除法运算符。
谢谢高手指教

158 个解决方案

#1

自己顶上，呵呵

#2

直接乘不就符合他的要求吗？？

#3

引用 2 楼 mymgrub 的回复:

直接乘不就符合他的要求吗？？

要求是线性复杂度，直接乘是O(n^2)

#4

用空间换时间的思想，建立一个二维数字b[m][n],存放的是b[m][n] = a[m]*a[m+1]*...*a[n]的值（m<n），一次循环就可以建立完这个上三角矩阵，然后再循环一次就可得结果，如a[0] = b[1][n-1],a[1]=a[0] * b[2][n-1]。此算法的时间复杂度为O（2n），线性。

#5

mark

#6

扫一遍，计算rec[i]为a[0]*a[1]...*a[i]，这是O(n)的。

然后计算结果b[i]的时候，b[i]=a[n]/b[i-1]; 这也是O(n)的。

考虑乘法结果会不会太大，考虑大数。

#7

然后计算结果b[i]的时候， b[i]=a[n]/a[i-1]; 这也是O(n)的。

#8

额，还可以优化，直接计算n个数的乘积total。

计算b[]的时候，顺便累积一个当前乘积cur即可，对于b[i]=total/cur; cur*=a[i];

#9

mark
楼上题目要求不能用除法 

#10

定义数组B
然后B【n-1】=0
temp=a[n-1];
B[n-2]=temp;
temp=a[n-1]*a[n-2];
B[n-3]=temp;
.......循环
然后复制B到A

#11

理解错了，。。

#12

额，把题目看颠倒了。

a[0]变为a[1]到a[n-1]的积 啊！！！

从n-1到0扫一遍不就结束了么。

#13

现写一个函数计算除N意外的所有数积
long fun(int *a,int m,int n)
{
  long temp = 1;
  int i;
  for(i=0; i<m, i++)
  {
    if(i == n) countent;
    temp = temp *a[i];
  }
  return temp;
}

接下来就是正常的调用更新，不知道这样行不行？

#14

引用 6 楼 qq120848369 的回复:

扫一遍，计算rec[i]为a[0]*a[1]...*a[i]，这是O(n)的。

然后计算结果b[i]的时候，b[i]=a[n]/b[i-1]; 这也是O(n)的。

考虑乘法结果会不会太大，考虑大数。

题目规定不能用除法

#15

引用 13 楼 studycbc 的回复:

现写一个函数计算除N意外的所有数积
long fun(int *a,int m,int n)
{
  long temp = 1;
  int i;
  for(i=0; i<m, i++)
  {
    if(i == n) countent;
    temp = temp *a[i];
  }
  return temp;
}

接下来就是正常的调用更新，不知道……

因为你这个函数中有for，所以复杂度不合题意

#16

看懂题目了。

1 2 3 4 5

a[3]=a[1]*a[2]*a[4]*a[5];

是这个意思吧。

从前往后扫一遍，计算b[i]=a[0]*a[1]*..a[i-1].
从后往前扫一遍，计算c[i]=a[i+1]*a[i+2]*...a[n-1]；

求a[i]=b[i]*c[i];

#17

3步搞定（假设乘法是一次运算）……
1、累乘：计算a1*a2, a1*a2*a3, ......, a1*a2*...*an——复杂度n-1
2、累乘：计算an*a(n-1), an*a(n-1)*a(n-2), ......, an*a(n-1)*a(n-2)*...*a1——复杂度n-1
3、求积：找到对应数值，直接再做一次乘法得结果——复杂度为n
这样，复杂度就是3n-2，也就是O(3n)

#4好像更简单一点，不过我不太理解怎么用O(n)来建立这个上三角矩阵，我觉得得O(2n)才可以吧？
求解释……

#18

引用 16 楼 qq120848369 的回复:

看懂题目了。

1 2 3 4 5

a[3]=a[1]*a[2]*a[4]*a[5];

是这个意思吧。

从前往后扫一遍，计算b[i]=a[0]*a[1]*..a[i-1].
从后往前扫一遍，计算c[i]=a[i+1]*a[i+2]*...a[n-1]；

求a[i]=b[i]*c[i];

好像复杂度不对啊，这个好像是O（n^2)

#19

引用 18 楼 jingsuxuyilq 的回复:

引用 16 楼 qq120848369 的回复:

看懂题目了。

1 2 3 4 5

a[3]=a[1]*a[2]*a[4]*a[5];

是这个意思吧。

从前往后扫一遍，计算b[i]=a[0]*a[1]*..a[i-1].
从后往前扫一遍，计算c[i]=a[i+1]*a[i+2]*...a[n-1]；

求a[i]=b[i]*c[i];

好像复杂度不对啊，……

O(2*n)=O（n）

#20

O(k*n)=O（n）

#21

引用 19 楼 qq120848369 的回复:

引用 18 楼 jingsuxuyilq 的回复:

引用 16 楼 qq120848369 的回复:

看懂题目了。

1 2 3 4 5

a[3]=a[1]*a[2]*a[4]*a[5];

是这个意思吧。

从前往后扫一遍，计算b[i]=a[0]*a[1]*..a[i-1].
从后往前扫一遍，计算c[i]=a[i+1]*a[i+2]*...a[n-1]；

求……

不好意思，我想问下你确定这样是O（2n）而不是O（n^2）？

#22

怎么又没人了啊。。。帅哥们果断跟帖

#23

引用 22 楼 tsx86 的回复:

怎么又没人了啊。。。帅哥们果断跟帖

16楼已经给出答案了

#24

引用 23 楼 bellbird 的回复:

引用 22 楼 tsx86 的回复:

怎么又没人了啊。。。帅哥们果断跟帖

16楼已经给出答案了

大哥，你仔细想想他的算法是不是有问题？要更新整个数组的元素，就是要把a[0]、a[1]```a[n-1]全部算出来啊。那按照16楼的这里是不是还需要一个循环呢？如果是单求数组中的一个元素还可以，如果全部算出来，他的算法貌似不行，不是吗？还请各位大牛赐教，这题蛮有意思的

#25

进不了搜狗了

#26

引用 24 楼 tsx86 的回复:

引用 23 楼 bellbird 的回复:
引用 22 楼 tsx86 的回复:

怎么又没人了啊。。。帅哥们果断跟帖

16楼已经给出答案了

大哥，你仔细想想他的算法是不是有问题？要更新整个数组的元素，就是要把a[0]、a[1]```a[n-1]全部算出来啊。那按照16楼的这里是不是还需要一个循环呢？如果是单求数组中的一个元素还可以，如果全部算出来，他的算法貌似不行，不是吗？还……

有道理

#27

按 17楼观点

#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
int a[7]={1,2,3,4,5,6,7};
int b[7],c[7];
int temp1=1;
int temp2=1;
for(int i=0;i<7;i++)
{
temp1=temp1*a[i];
b[i]=temp1;
temp2=temp2*a[6-i];
c[i]=temp2;
}
for(int i=0;i<7;i++)
{
if(i==0)
a[0]=c[5];
if(i==6)
a[6]=b[5];
if(i>0&&i<6)
a[i]=c[5-i]*b[i-1];
cout<<a[i]<<' ';
}
cout<<endl;
return 0;
}

#28

但是对于大数就不适用了 

#29

建立一个同样大小的数组b[n],第一次循环，将a中符合条件的乘积值放到b中，
b[0]=a[1]*a[2]...*a[n-1]
...
b[n-1]=a[0]*a[1]...*a[n-2]
第二次循环将b中各元素赋值给a中对应的元素。

#30

17楼不就是正确答案吗？
4楼的没看懂.

#31

17楼正解，顶他

#32

public void reValue(int[] a){

		int[] b = new int[a.length];
		int[] c = new int[a.length];
		b[0] = a[0];
		c[0] = a[a.length-1];
		for(int i =1;i<a.length;i++){
			b[i]=b[i-1]*a[i];
			c[i]=c[i-1]*a[a.length-i-1];
		}
		a[0] = c[a.length-2];
		for(int i =1;i<a.length-1;i++){
			a[i]=b[i-1]*c[a.length-2-i];
		}
		a[a.length-1] = b[a.length-2];
	}

时间复杂度为O（2n）

#33

引用 4 楼 echoyin59 的回复:

用空间换时间的思想，建立一个二维数字b[m][n],存放的是b[m][n] = a[m]*a[m+1]*...*a[n]的值（m<n），一次循环就可以建立完这个上三角矩阵，然后再循环一次就可得结果，如a[0] = b[1][n-1],a[1]=a[0] * b[2][n-1]。此算法的时间复杂度为O（2n），线性。

你的复杂度可次是2N，帅哥，是 M*N，如果是N=M的话，那就不是线性了 = N的平方了

#34

MARK

#35

#include <iostream>
using namespace std;

void main()
{
int n = 10;

int * a = new int[n];
int * b = new int[n];
int * c = new int[n];

for (int i = 0;i < n;i++)
{
a[i] = 2;
}

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

c[n - 1] = 1;
c[n - 2] = a[n - 1];
for (int i = n - 3;i >= 0;i--)
{
c[i] = c[i + 1] * a[i + 1];
}

for (int i = 0;i < n;i++)
{
a[i] = b[i] * c[i];
cout<<a[i]<<" ";
}
cout<<endl;

delete[] a;
delete[] b;
delete[] c;
}

#36

#include <iostream>
using namespace std;

void main()
{
	int n = 10;

	int * a = new int[n];
	int * b = new int[n];
	int * c = new int[n];

	for (int i = 0;i < n;i++)
	{
		a[i] = 2;
	}

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

	c[n - 1] = 1;
	c[n - 2] = a[n - 1];
	for (int i = n - 3;i >= 0;i--)
	{
		c[i] = c[i + 1] * a[i + 1];
	}

	for (int i = 0;i < n;i++)
	{
		a[i] = b[i] * c[i];
		cout<<a[i]<<" ";
	}
	cout<<endl;

	delete[] a;
	delete[] b;
	delete[] c;
}

#37

引用 16 楼 qq120848369 的回复:

看懂题目了。

1 2 3 4 5

a[3]=a[1]*a[2]*a[4]*a[5];

是这个意思吧。

从前往后扫一遍，计算b[i]=a[0]*a[1]*..a[i-1].
从后往前扫一遍，计算c[i]=a[i+1]*a[i+2]*...a[n-1]；

求a[i]=b[i]*c[i];

这个靠谱。

#38

mark

#39

楼上的复杂度也不符合呀，相当于(n-1)*n，照这个复杂度最普通的算法都可以呀

#40

引用 17 楼 mesh4444 的回复:

3步搞定（假设乘法是一次运算）……
1、累乘：计算a1*a2, a1*a2*a3, ......, a1*a2*...*an——复杂度n-1
2、累乘：计算an*a(n-1), an*a(n-1)*a(n-2), ......, an*a(n-1)*a(n-2)*...*a1——复杂度n-1
3、求积：找到对应数值，直接再做一次乘法得结果——复杂度为n
这样，复杂度就是3n-2，也就是O(……

我想问下你这是想把所有的乘积都记录？如果是的话靠谱吗？这样需要多少个变量有想过没？

#41

不好意思，好像可以用数组。我再看看

#42

17楼的想法貌似可以。
1、累乘：计算a1*a2, a1*a2*a3, ......, a1*a2*...*an——复杂度n-1
2、累乘：计算an*a(n-1), an*a(n-1)*a(n-2), ......, an*a(n-1)*a(n-2)*...*a1——复杂度n-1
把上面两步计算的每个乘积存放在两个新的数组中。比如b[0]=a[0];b[1]=b[0]*a[1];b[2]=b[1]*a[2];
c[0]=a[n-1];c[1]=c[0]*a[n-1]```
楼主你看看理解了没？

#43

４楼的算法跟１７楼的应该是一样的，不过没１７楼说的明白

#44

要求具有线性复杂度什么意思》？

#45

前后走一遍就行了，o(n)

#46

引用 16 楼 qq120848369 的回复:

看懂题目了。

1 2 3 4 5

a[3]=a[1]*a[2]*a[4]*a[5];

是这个意思吧。

从前往后扫一遍，计算b[i]=a[0]*a[1]*..a[i-1].
从后往前扫一遍，计算c[i]=a[i+1]*a[i+2]*...a[n-1]；

求a[i]=b[i]*c[i];

第三步和第二步可以合并，
创建一个n长的数组存储从前向后的乘积结果，
然后创建一个变量，保存从后到前面的乘积就可以了，同时可以置换a[i]的值

#47

#include "stdafx.h"
#include <iostream>

using namespace std;


void ChangeArray(int arr[], int len)
{
	//临时数组存放从右向左的乘积
	int *temp = new int[len];
	temp[len - 1] = arr[len - 1];
	for (int i = len - 2; i >= 0; --i)
	{
		temp[i] = arr[i] * temp[i+1];
	}

	//临时变量存放从左向右的乘积
	int left = arr[0];
	arr[0] = temp[1];

	//进行计算
	int cur = 0;
	for (int i = 1; i < len - 1; i++)
	{
		cur = arr[i];
		arr[i] = left * temp[i+1];
		left = left * cur;
	}
	arr[len -1] = left;
}
int main()
{
	int arr[] = {1, 2, 3, 4, 5, 6};
	int len = sizeof(arr) / sizeof(int);

	ChangeArray(arr, len);

	for (int i = 0; i < len; ++i)
		cout<<arr[i]<<" ";
	cout<<endl;
}

#48

建二维数组，是o（n*n）

引用 4 楼 echoyin59 的回复:

用空间换时间的思想，建立一个二维数字b[m][n],存放的是b[m][n] = a[m]*a[m+1]*...*a[n]的值（m<n），一次循环就可以建立完这个上三角矩阵，然后再循环一次就可得结果，如a[0] = b[1][n-1],a[1]=a[0] * b[2][n-1]。此算法的时间复杂度为O（2n），线性。

#49

不能用除法，你用了除法，另外，除法可能会导致结果不对

引用 8 楼 qq120848369 的回复:

额，还可以优化，直接计算n个数的乘积total。

计算b[]的时候，顺便累积一个当前乘积cur即可，对于b[i]=total/cur; cur*=a[i];

#50

16,17楼的
一个想法，可以