数组乘积--满足result[i] = input数组中除了input[i]之外所有数的乘积(假设不会溢出

数组乘积(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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习实践二三事

python基础----函数作为返回值

从一个例子讲起 高阶函数除了可以接受函数作为参数外,还可以把函数作为结果值返回。 还是考虑这个问题:对可变参数进行求和 看了上一讲的已经知道,可以使用’*’...

29550
来自专栏流媒体

C++多态

当类存在虚函数时,编译器会为该类维护一个表,这个表就是虚函数表(vtbl),里面存放了该类虚函数的函数指针。在构造类的时候增加一个虚表指针(vptr)指向对应的...

12430
来自专栏十月梦想

运算符

=就是简单给变量的赋值,+(-,*,/,%,.)=等同于左边加上(减去,乘上,除以,求余数,字符连接)右边赋值给昨天

7630
来自专栏Python小屋

详解Python函数式编程之map、reduce、filter

map()、reduce()、filter()是Python中很常用的几个函数,也是Python支持函数式编程的重要体现。不过,在Python 3.x中,red...

39360
来自专栏小樱的经验随笔

【Java学习笔记之十】Java中循环语句foreach使用总结及foreach写法失效的问题

foreach语句使用总结 增强for(part1:part2){part3}; part2中是一个数组对象,或者是带有泛性的集合. part1定义了一...

28670
来自专栏北京马哥教育

正则表达式基本语法

\将下一字符标记为特殊字符、文本、反向引用或八进制转义符。例如,“n”匹配字符“n”。“\n”匹配换行符。序列“\\”匹配“\”,“\(”匹配“(”。^匹...

36470
来自专栏androidBlog

二分查找的相关算法题

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

16310
来自专栏Golang语言社区

Python基本运算符

什么是操作符? 简单的回答可以使用表达式4 + 5等于9,在这里4和5被称为操作数,+被称为操符。 Python语言支持操作者有以下几种类型。 算术运算符 比较...

49370
来自专栏向治洪

数据结构之数组

一.数组的基本概念 数组可以看成是多个相同类型数据组合,对这些数据的统一管理。 数组变量属引用类型,数组也可以看成是对象,数组中的每个元素相当于该对象的成员变...

23150
来自专栏lonelydawn的前端猿区

js高精度浮点数运算

贴代码:  // 自定义高精度浮点数运算 // 对象格式写法 var float_calculator={ /** * 1.记录两个运算数小数点后的位数 ...

673100

扫码关注云+社区

领取腾讯云代金券