数组乘积（15分）
输入：一个长度为n的整数数组input
输出：一个长度为n的整数数组result，满足result[i] = input数组中除了input[i]之外所有数的乘积（假设不会溢出）。比如输入：input = {2,3,4,5}，输出result = {60,40,30,24}
程序时间和空间复杂度越小越好。
1 /* 2 * 一个长度为n的整数数组result，满足result[i]=除input[i]之外所有数的乘积（不溢出），比如 3 * 输入input={2,3,4,5};输出 result={60,40,30,24}; 4 */ 5 /* 6 * 方法一：判断有0的情况，如果有0则其他都为0.如果没0,可使用先求全部乘积，再除以自身。 7 * 方法二：先保存i位置前的乘积到result[i]，再用一变量保存i位置后的乘积，结果相乘，即可。 8 */ 9 #include <stdio.h> 10 //#include <stdlib.h> 11 void pr_arr(int arr[],int n) 12 { 13 int i; 14 for( i=0;i<n;i++) 15 { 16 printf("%d ",arr[i]); 17 } 18 printf("\n"); 19 } 20 21 void arrayMultiply(int input[],int result[],int n)//方法二 22 { 23 if(n<=0) return; 24 result[0]=1; 25 int i; 26 for( i =1;i<n;i++) //从1位置开始，result[i]表示input i位置前的乘积 27 { 28 result[i]=result[i-1]*input[i-1]; 29 } 30 int q=1; 31 for( i=n-2;i>=0;--i) //从倒数第二个开始，q表示input i位置后的乘积 32 { 33 q*=input[i+1]; 34 result[i]*=q; 35 } 36 pr_arr(result,n); 37 } 38 int main(void) { 39 int s[]={2,3,4,5,7,8,6}; 40 int n=sizeof(s)/sizeof(int); 41 42 int *result = new int[n]; 43 arrayMultiply(s,result,n); 44 return 0; 45 }
其中小米2013年校园招聘出了类似的题：
| 数组乘积（15分） 输入：一个长度为n的整数数组input 输出：一个长度为n的整数数组result，满足result[i] = input数组中除了input[i]之外所有数的乘积（假设不会溢出）。比如输入：input = {2,3,4,5}，输出result = {60,40,30,24} 程序时间和空间复杂度越小越好。 C/C++： int *cal(int* input , int n); Java: int[] cal(int[] input); |
参考代码：
int *cal(int* input , int n)
{
if(input == NULL || n < 0)
return;
int i ;
int *result = new int[n];
result[0] = 1;
for(i = 1 ; i < n ; ++i)
result[i] = result[i-1]*input[i-1];
result[0] = input[n-1];
for(i = n-2 ; i > 0 ; --i)
{
result[i] *= result[0];
result[0] *= input[i];
}
return result;
}
测试代码：
#include<iostream>
using namespace std;
int *cal(int *input , int n)
{
int i;
int *result = new int[n];
result[0] = 1;
for(i = 1 ; i < n ; ++i){
result[i] = result[i - 1] * input[i - 1];
}
result[0] = input[n - 1];
for(i = n - 2 ; i > 0 ; --i){
result[i] *= result[0];
result[0] *= input[i];
}
//return result;
for(int i = 0 ; i < n ; ++i)
cout<<result[i]<<",";
cout<<endl;
return 0;
}
int main()
{
int input[] = {2 , 3 , 4 , 5};
int length = sizeof(input) / sizeof(int);
*cal(input , length);
return 0;
}
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
