小米13笔试编程题 1
浏览数：53 /
时间：2015年06月11日
数组乘积（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);
方法1：算出数组所有元素乘积sum，再逐个除以对应元素sum/input[i]，如下
#include<iostream> using namespace std; int *cal(int* input , int n){ int sum=1; int *result=new int[n]; for(int i=0;i<n;i++){ sum=sum*input[i]; } cout<<sum<<endl; for(int j=0;j<n;j++){ result[j]=sum/input[j]; } return result; } int main(){ int input[]={2,3,4,5}; int L=sizeof(input)/sizeof(input[0]);//计算数组长度 int *re=cal(input,L); cout<<re[0]<<re[1]<<re[2]<<re[3]<<endl;//字符数组可直接输出数组名，其他的输出地址 }
方法2：得出数组中该元素之前所有元素乘积，再用循环实现，对于输入2，3，4，5 即先得到5，2，2*3，2*3*4（最后一个元素置首位），再从元素末尾的前一个元素开始计算（原理是用该元素前面所有元素乘积，再乘以该元素后面所有元素乘积）。
#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]; //reslut[i]中存的是当前元素前面所有的乘积；result[0]是当前元素后面所有的乘积，将二者相乘即可 result[0] *= input[i]; } return result; } int main(){ int input[]={2,3,4,5}; int L=sizeof(input)/sizeof(input[0]);//计算数组长度 int *re=cal(input,L); cout<<re[0]<<re[1]<<re[2]<<re[3]<<endl;//字符数组可直接输出数组名，其他的输出地址 }
reslut[i]中存的是当前元素前面所有的乘积；result[0]是当前元素后面所有的乘积，将二者相乘即可
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
