算法-从N个整数中找了(n-1)个元素乘积最大的那一组?

算法-从N个整数中找了(n-1)个元素乘积最大的那一组?

浮生未歇 发布于 2017-05-30 字数 229 浏览 1147 回复 4

今天从朋友那听说了一道Google的面试题:拿来讨论一下

题目:长度为n的整数数组,找出其中任意(n-1)个乘积最大的那一组,只能用乘法,不可
以用除法。要求对算法的时间复杂度和空间复杂度作出分析,可以写思路也可以写程序。

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

偏爱自由 2017-09-19 4 楼

这个问题在网上的讨论已经很多了,比如
http://topic.csdn.net/t/20061203/15/5203069.html

但是总的来说,讨论的结果是仁者见仁。
之前在<<编程之美>>上看到过这个题目的解法,由于格式问题,粘贴不便,截图分享下:

偏爱自由 2017-09-07 3 楼

时间空间复杂度都为O(n)
s1[i]:从前往后遍历到i位置的乘积(0<=i<n)
s2[j]:从后往前遍历到j位置的乘积(0<=j<n)
最后遍历一遍找出s1[k+1]*s2[k-1]的最小值(0<k<n-1),讲结果与s1[1]和s2[n-2]比较大小,最大的那个即为最大值。

灵芸 2017-08-13 2 楼

提供一个O(N)的解决方案,大家一起来看看。

分析:由于序列中是n个正数,要求n-1个的乘积最大值,那么找出一个合适的值,剩下的就是乘积最大的序列。

下面的各种情况代编号的是基本情况,【case】是基本情况的合并。

【case 1, 全部是正数】
1、全部是正数:
Action:找出最小正数;

【case 2-1,含0,负数个数为偶数】
2、正数、0:找出0;
4、负数、0:
6、正数、负数、0
Action:负数的个数为偶数,所有负数乘积是正的,找到0,剩余的结果为正(或为0,原来有多个0);

【case 2-2, 含0,负数个数为奇数】
4、负数、0:
6、正数、负数、0:
Action:负数的个数为奇数,所有负数乘积是负的,去掉任一个负数(第一个就OK),结果为0;

【case3-1,不含0,负数个数为奇数】
3、全部是负数:
5、正数、负数:
负数的个数为奇数,所有负数乘积是负的,找到最大的负数(绝对值最小),剩下的负负得正,绝对值相对大;

【case3-1,不含0,负数个数为偶数】
3、全部是负数:
5、正数、负数:
负数的个数为偶数,所有负数乘积是正的,找到最小的负数(绝对值最大),剩下的负数乘积为负,绝对值相对小;

因此,针对该序列:
第一步,需要获得一下这些值,
1、判断是否全是正数;
2、判断序列中是否含有0,如果有,还有其位置;
3、获得序列中负数的个数;
4、获得序列中的最小正数及其位置;
5、获得序列中的最大负数和最小负数及其位置;

第二步,根据上面的分析结果,和第一步得出的值确定,要删除的位置;
第三步,在数组中删除那个位置数据,并返回数组。

int[] max_projuct_array(int a[], int n) {
// 1, get features of the array
bool isAllPositive = false;
int posMin = 0;
int posMinPos = -1;

bool hasZero = false;
int firstZeroPos = -1;

int negCount = 0;
int firstNegPos = -1;
int negMin = 0;
int negMinPos = -1;
int negMax = 0;
int negMaxPos = -1;

int theRemovedPos = -1;

for (int i=0; i<n; ++i) {
if (a[i] == 0 && !hasZero) {
hasZero = true;
firstZero = i;
} else if (a[i] < 0) {
++negCount;
if (negCount == 1) {firstNeg = i;}
if (a[i] < negMin) {negMin = a[i]; negMinPos = i;}
if (a[i] > negMax || negMax == 0) {negMax = a[i]; negMaxPos = i;}
} else {
if (a[i] < posMin || posMin == 0) {posMin = a[i]; posMinPos = i;}
}
}

if (!hasZero && negCount == 0)
isAllPositive = true;

// 2, find the elimated element according to the features
if (isAllPositive) {
theRemovedPos = posMinPos;
} else if (hasZero) {
if ((negCount&1) == 1)
theRemovedPos = firstNegPos;
else
theRemovedPos = firstZeroPos;
} else {
if ((negCount&1) == 1)
theRemovedPos = negMaxPos;
else
theRemovedPos = negMinPos;
}

// 3, remove the elements and return;
for (i=theRemovedPos; i<n; ++i)
a[i] = a[i+1];

return a;
}

虐人心 2017-07-21 1 楼

写了个java版的,大致能出结果,不知道有没有bug.

package com.puzzle;

public class Max {

public int symbol = 1;//结果的最终符号
public int minimunPositive;//最小的正数
public int maxNegative = 0;//最大的负数
private boolean zeroFlag = false;//是否遇到0

//返回应该去掉的那个数
public int calculate(int[] input) {
System.out.println("Calculating!");
this.minimunPositive = input[0];
this.maxNegative = 0;
for(int i = 0; i < input.length; i++)
{
if(input[i] < 0)
{
//最大負數初始化
if(this.maxNegative == 0)
{
this.maxNegative = input[i];
}
//如果小于0,改变符号
this.symbol *= -1;
//如果小于0,且大于当前的最大负数,则把当前值赋给最大负数
if(input[i] > this.maxNegative)
{
this.maxNegative = input[i];
}
}
if(input[i] == 0)
{
this.zeroFlag = true;
}

//如果当前值大于0,且小于最小正数,则将该值赋给最小正数
if(input[i] > 0)
{
if(input[i] < this.minimunPositive)
{
this.minimunPositive = input[i];
}
}
}
//如果結果符號位負數
if(this.symbol == -1)
{
if(this.zeroFlag)
{

}
return this.maxNegative;
}
//如果結果符號位正
if(this.symbol == 1)
{
if(this.zeroFlag)
return 0;
else
{
return this.minimunPositive;
}
}

return 0;
}

public static void main(String[] args)
{
Max max = new Max();
int[] input = {1,2,3,4,5,1,1,90, 6,7,8};
System.out.println("Result:" + max.calculate(input));
System.out.println("Symbol" + max.symbol);
System.out.println("Max Negative:" + max.maxNegative);
System.out.println("Min Positive:" + max.minimunPositive);
}
}