题目
给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合乘积中的最大的一组,并写出算法的时间复杂度。
思路一 穷举法
我们把所有可能的(N-1)个数的组合找出来,分别计算它们的乘积,并比较大小。由于总共有N个(N-1)个数的组合,总的时间复杂度为O(N^2),但显然这不是最好的思路。
思路二 空间换时间
计算(N-1)个数的组合乘积,假设第i个(0<=i<=N-1)元素被排除在乘积之外(如下图)。
设num[]为初试数组
Left[i]表示前i个元素(包括第i个元素)的乘积(0<=i<=N-1)
Left[i] = Left[i-1] * num[i]
Right[i]表示后N-i个元素(包括第i个元素)的乘积(0<=i<=N-1)
Right[i] = Right[i+1] * num[i]
设p[i]为数组除第i个元素外,其他N-1个元素的乘积:
P[i] = Left[i-1] * Right[i+1]
举个例子:
P[4] = Left[3] * Right[5]
= a1 * a2 * a3 * a4 * a6 * a7 * a8 * a9 * a10
由于只需要从头到尾,从尾到头扫描两次即可得到数组Left[] 和 Right[],从而线性时间得到P[i]。所以很容易的就可以得到最大值(只需遍历一次p数组)。总的时间复杂度为计算数组Left[],Right[],p[]的时间复杂度加上查找p[]最大值的时间复杂度即O(N)。
代码一
#include <iostream>
#include <cstring>
using namespace std;
class Solution {
public:
double MaxProduct(double num[],int n){
if(n <= 0){
return 0;
}
double max = num[0],p;
double Left[n],Right[n];
Left[0] = num[0];
Right[n-1] = num[n-1];
for(int i = 1;i < n;++i){
Left[i] = Left[i-1] * num[i];
}
for(int i = n-2;i >= 0;--i){
Right[i] = Right[i+1] * num[i];
}
int left,right;
for(int i = 0;i < n;++i){
left = (i - 1) >= 0 ? Left[i-1] : 1;
right = (i + 1) < n ? Right[i+1] : 1;
p = left * right;
if(p > max){
max = p;
}
}
return max;
}
};
int main() {
Solution solution;
double num[] = {-2.5,-4,0.5,3,1,2,-3};
cout<<solution.MaxProduct(num,7)<<endl;
}
思路二
通过分析,进一步减少计算量。假设N个数的乘积为P,针对P的正负性进行如下分析:
(1)P为0
那么,数组中至少包含一个0。假设除去一个0之外,其他N-1个数的乘积为Q,根据Q的正负性进行讨论:
Q为0,说明数组中至少有两个0,那么N-1个数的乘积只能为0。
Q为正,返回Q。因为如果用0替换剩余N-1个数中的任意一个,所得乘积结果都为0,小于之前的Q,因此乘积最大值为Q。
Q为负,返回0。因为如果用0替换剩余N-1个数中的任意一个,所得结乘积果都为0,大于之前的Q,因此乘积最大值为0。
(2)P为负
根据“负负得正”的乘法性质,自然想到的是从N个整数中去掉一个负数,使得N-1个数乘积为正数。而要使这个整数最大,这个被去掉的负数绝对值必须是数组中最小的。我们只需要扫描一遍数组,把绝对值最小的负数去掉就可以了。
(3)P为正
类似P为负的情况,应该去掉一个绝对值最小的正数值,这样得到的N-1个数乘积就是最大的。
上面的思路采用了直接求N个数的乘积P,进而判断P的正负性的办法,但是直接求乘积往往有溢出的危险,事实上可做一个小的转变,不需要直接乘积,而是求出数组中正数,负数和0的个数,从而判断P的正负性。
在时间复杂度上,由于只需要一次遍历数组,在遍历数组的同时就可得到数组中正数,负数和0的个数,以及数组中绝对值最小的正数和负数,时间复杂度为O(N)
代码二
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
class Solution {
public:
double MaxProduct(double num[],int n){
if(n <= 0){
return 0;
}
double pMin = INT_MAX,nMin = INT_MAX;
int pIndex = 0,nIndex = 0,zeroIndex;
int zCount = 0,pCount = 0,nCount = 0;
int index = 0;
for(int i = 0;i < n;++i){
if(num[i] == 0){
zeroIndex = i;
++zCount;
}
else if(num[i] > 0){
++pCount;
if(num[i] < pMin){
pIndex = i;
pMin = num[i];
}
}
else{
++nCount;
if(fabs(num[i]) < nMin){
nMin = fabs(num[i]);
nIndex = i;
}
}
}
if(zCount > 0){
if(zCount - 1 > 0){
return 0;
}
if(nCount % 2){
return 0;
}
else{
index = zeroIndex;
}
}
else if(nCount % 2 == 0){
index = pIndex;
}
else{
index = nIndex;
}
double max = 1;
for(int i = 0;i < n;++i){
if(i != index){
max *= num[i];
}
}
return max;
}
};
int main() {
Solution solution;
double num[] = {2.5,4,-0.5,3,-1,2,3};
cout<<solution.MaxProduct(num,7)<<endl;
}
相似题目
[经典面试题]最大连续乘积
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
算法 子数组最大乘积
给定一个n个元素的数组,数组元素全部为整数,负数,正数和0均有可能存在,设设计一个算法,找出连续的几个数组元素相乘积最大
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。 2、代码详解 法一:可扩展性好(推荐) 二维数组,2*2大小,一维存最大值,一维存负最大值 class Solution(object)...
示例 1:输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。示例 2:输入: [-2,0,-1]输出: 0解释: 结果不能为 2
用数据解决乘积超出数据的最大范围,此为100的阶乘,同理更大数的阶乘以此类推!
示例:输入: [1,2,3,4]输出: [24,12,8,6]算法1:暴力法- 不出意料的超时改进思路1:- 除自身以外的乘积 = 自身左边的乘积 * 自身右边
除自身以外数组的乘积 给你一个整数数组 nums,返回数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数...
java基础面试题构建乘积数组本资源系百度网盘分享地址
面试题66. 构建乘积数组题目链接面试题66. 构建乘积数组题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B
乘积最大子数组.md
javascript javascript_leetcode面试题解动态规划问题之第152题乘积最大子数组_题解
向您详细介绍微软测试题,相信您一定会有所收获。
Java-Leetcode-乘积最大子数组.zip
java java_leetcode面试题解双指针之第713题乘积小于k的子数组
用户输入2个二维数组,程序自动输出这2个数组的乘积
# 除自身以外数组的乘积 # 给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output , # 其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 # 输入示例 # [1,2,3,4] # 输出示例 # [24,12,8,6]...
[构建乘积数组]完整的可执行代码(Java) 解题思路见文章:https://blog.csdn.net/flower_48237/article/details/104065815 题目描述: 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B...
152. 乘积最大子数组public int maxProduct(int[] nums) {//也可以用数组代替//下面mx会改变所以需要先存储起来;//三种
剑指offer面试题66--构建乘积数组给定一个数组A[0, 1,...n - 1],请构建一个数组A[0, 1,...n - 1],其中B中的元素B[i] =