[摆个擂台]设有一整数数组，元素个数为N，求其中N-1个元素相乘的最大乘积
这是一个Google笔试题，我5年前看到的。
设有一整数数组，元素个数为N，求其中N-1个元素相乘的最大乘积。
例如：输入数组[2,4,5,3]；则返回60，（对应的N-1个元素是[3,4,5]，它比[2,3,4],[2,3,5],[2,4,5]三种组合的乘积都大）。
要求：
1. 时间复杂度尽可能低
2. 不可使用任何PHP自带的数组函数，能使用if, for, switch这样的控制结构，和isset/is_array/is_int这样的基本类型检查函数
函数模板：
<?php
class NumUtil
{
/**
* @param array $arr
* @return integer
*/
static public function findMaxProd(){/*你的代码*/}
}
分割线
单元测试我写好了，敢上擂台的同学，把代码贴到下面，我来检查能通过几个单元测试，哈哈。
挑擂结果（有两个测试用例我只占了个位，没写具体的数据。下面的结果都不包含这两个用例）updated @ 2013-3-22 16:32
JoyQi 目前最接近标准答案的，只有2个测试用例没通过，时间复杂度，我目测是没到最小，但跟我写的也不相伯仲，如果用C语言来实现，是循环更耗费时间还是大数相除更耗费时间就不好说了。
Sunyanzi 的还差三个测试用例没通过
公布答案了：单元测试/**
* 函数名释义：
* az: Amount of Zero, 零的个数
* ap: Amount of Positive, 正整数个数
* an: Amount of Negative, 负数个数
*
* gt: Greater Than, 大于
* eq: Equal, 等于
* lt: Less Than, 小于
*
* o: odd, 奇数
* e: even, 偶数
*
* #################### MECE Tree ####################
*参数输入正确的正常流程
* 零的个数大于1 @see TestCaseNumUtil::test_amountOfZeroGreaterThanOne()
* 零的个数等于1
* 负数个数为偶数
* 有正数 @see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsEven_existsPositive()
* 无正数 @see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsEven_notExistsPositive()
* 负数个数为奇数
* 有正数 @see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_existsPositive()
* 无正数 @see TestCaseNumUtil::test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_notExistsPositive()
* 零的个数小于1
* 负数个数为偶数
* 有正数 @see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsEven_existsPositive()
* 无正数 @see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsEven_notExistsPositive()
* 负数个数为奇数
* 有正数 @see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_existsPositive()
* 无正数 @see TestCaseNumUtil::test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_notExistsPositive()
*
*参数输入错误的异常流
* 输入的参数不是数组 @see TestCaseNumUtil::test_inputIsNotArray()
* 是个数组
* 元素个数小于2个 @see TestCaseNumUtil::test_ArrayContainLessThanTwoInteger()
* 元素多于2个
* 不全是整数 @see TestCaseNumUtil::test_ArrayContainNonInteger()
*
*白盒测试
* 元素个数超过int型上限 @see TestCaseNumUtil::test_amountOfZeroGreaterThanMaxInt()
* 元素的乘积超过PHP上限 @see TestCaseNumUtil::test_prodGreaterThanMaxInt()
*
* #################### MECE Tree ####################
*/
class TestCaseNumUtil extends PHPUnit_Framework_TestCase
{
/**
* 零的个数大于1
* 本来根据根据负数个数奇偶性、正数有无可以分成四种情况
* 但这四种情况明显可以归并到这一种，因此不再分成四个条件来写
*/
public function test_amountOfZeroGreaterThanOne()
{
$arr = array_merge(
$this->produceIntArray(rand(2, 10), self::INT_SIGN_ZERO),
$this->produceIntArray(rand(10, 20), self::INT_SIGN_RAND)
);
$this->assertEquals(0, NumUtil::findMaxProd($arr));
}
/**
* 零的个数等于1 偶数个负数 有正数
*/
public function test_amountOfZeroEqualsOne_amountOfNegativeIsEven_existsPositive()
{
$this->execTest(200, array(0, -1, -2, 10, 5, 2));
}
/**
* 零的个数等于1 偶数个负数 无正数
*/
public function test_amountOfZeroEqualsOne_amountOfNegativeIsEven_notExistsPositive()
{
$this->execTest(100, array(0, -1, -2, -10, -5));
}
/**
* 零的个数等于1 奇数个负数 有正数
*/
public function test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_existsPositive()
{
$arr = array_merge(
$this->produceIntArray(11, self::INT_SIGN_NEGA),
array(0),
$this->produceIntArray(rand(1,10), self::INT_SIGN_POSI)
);
$this->assertEquals(0, NumUtil::findMaxProd($arr));
}
/**
* 零的个数等于1 奇数个负数 无正数
*/
public function test_amountOfZeroEqualsOne_amountOfNegativeIsOdd_notExistsPositive()
{
$arr = array_merge(
$this->produceIntArray(11, self::INT_SIGN_NEGA),
array(0)
);
$this->assertEquals(0, NumUtil::findMaxProd($arr));
}
/**
* 零的个数小于1 偶数个负数 有正数
*/
public function test_amountOfZeroLessThanOne_amountOfNegativeIsEven_existsPositive()
{
$this->execTest(100, array( -1, -2, -10, -5, 10));
}
/**
* 零的个数小于1 偶数个负数 无正数
*/
public function test_amountOfZeroLessThanOne_amountOfNegativeIsEven_notExistsPositive()
{
$this->execTest(-10, array( -1, -2, -1024, -5));
}
/**
* 零的个数小于1 奇数个负数 有正数
*/
public function test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_existsPositive()
{
$this->execTest(200, array(-2, -10, -5, 4), self::INT_SIGN_POSI);
}
/**
* 零的个数小于1 奇数个负数 无正数
*/
public function test_amountOfZeroLessThanOne_amountOfNegativeIsOdd_notExistsPositive()
{
$this->execTest(50, array(-2, -10, -5), self::INT_SIGN_POSI);
}
public function test_inputIsNotArrayDataProvider()
{
return array(
array(NULL),
array(TRUE),
array(1024),
array(3.14),
array("not an array"),
array(new TestCaseNumUtil),
);
}
/**
* 输入的参数不是数组
* @dataProvider test_inputIsNotArrayDataProvider
* @expectedException PHPUnit_Framework_Error
*/
public function test_inputIsNotArray($arg)
{
NumUtil::findMaxProd($arg);
}
/**
* 数组元素个数小于2个
*/
public function test_ArrayContainLessThanTwoInteger()
{
$this->assertFalse(NumUtil::findMaxProd(array(10)));
}
/**
* 数组元素不全是整数
*/
public function test_ArrayContainNonInteger()
{
$this->assertFalse(NumUtil::findMaxProd(array(-2, TRUE, -5)));
}
/**
* 如果代码中用整形来记录【零、正数、负数】的个数，输入的数组元素个数超过int型上限，就会造成数据溢出
*/
public function test_amountOfZeroGreaterThanMaxInt()
{
//这种极端情况不支持，也不测试，写在这里仅仅表示我考虑到这点了
}
/**
* N-1个元素的乘积超过PHP能表达的上限，就会造成数据溢出
*/
public function test_prodGreaterThanMaxInt()
{
//这种情况暂时不支持，也不测试，写在这里仅仅表示我考虑到这点了
}
const INT_SIGN_POSI = "positive";
const INT_SIGN_NEGA = "negative";
const INT_SIGN_ZERO = "zero";
const INT_SIGN_RAND = "RAND";
private function produceIntArray($length, $sign)
{
$int_arr = array();
switch($sign)
{
case self::INT_SIGN_POSI :
for($i = 0; $i < $length; $i++)
{
$int_arr[$i] = rand(1, 99);
}
break;
case self::INT_SIGN_NEGA :
for($i = 0; $i < $length; $i++)
{
$int_arr[$i] = 0 - rand(1, 99);
}
break;
case self::INT_SIGN_ZERO :
for($i = 0; $i < $length; $i++)
{
$int_arr[$i] = 0;
}
break;
case self::INT_SIGN_RAND :
for($i = 0; $i < $length; $i++)
{
$int_arr[$i] = $i % 2 ? rand(1, 99) : 0 - rand(0, 99);
}
break;
}
return $int_arr;
}
private function execTest($exp, array $arr, $sign = self::INT_SIGN_NEGA)
{
$randInt = self::INT_SIGN_POSI == $sign ? rand(1, 100) : 0 - rand(1, 99);
$arr[] = $randInt;
$arr[] = $randInt;
shuffle($arr);
$this->assertEquals($exp * $randInt * $randInt, NumUtil::findMaxProd($arr));
}
}
公布答案了：我的函数实现
class NumUtil
{
/**
* @param array $arr
* @return integer
*/
static public function findMaxProd(array $arr)
{
$arr_len = count($arr);
if (2 > $arr_len)
{
return false;
}
/*
* 先遍历数组找出零、负数、正数的数量
* 只做统计，不排序，不做乘法
*/
$amount_zero = 0;//零的个数
$amount_negative = 0;//负数个数
$amount_positive = 0;//正数个数
$min_positive_index = null;
$min_negative_index = null;
$max_negative_index = null;
$the_only_zero_index = null;
for($i = 0; $i < $arr_len; $i++)
{
if (!is_int($arr[$i]))
{
return false;
}
if (0 > $arr[$i])
{
$amount_negative += 1;
if (is_null($min_negative_index) || $arr[$i] < $arr[$min_negative_index])
{
$min_negative_index = $i;
}
if (is_null($max_negative_index) || $arr[$i] > $arr[$max_negative_index])
{
$max_negative_index = $i;
}
}
else if (0 == $arr[$i])
{
$amount_zero += 1;
$the_only_zero_index = $i;
}
else
{
$amount_positive += 1;
if (is_null($min_positive_index) || $arr[$i] < $arr[$min_positive_index])
{
$min_positive_index = $i;
}
}
}
/**
* Logical control start
*/
if (1 < $amount_zero)
{
/*
* 0的个数大于1，任意取N-1个元素，其乘积都是0
* 故无须再判断正数和负数的个数
*/
return 0;
}
else if (1 == $amount_zero)
{
if (1 == $amount_negative % 2)
{//奇数个负数
/*
* 最大乘积只能是0，无需判断正数个数
*/
return 0;
} else {//偶数个负数
/*
* 除0之外的N-1个整数乘积最大
*/
$pick_out_index = $the_only_zero_index;
}
}
else// if (1 > $amount_zero)
{
if (1 == $amount_negative % 2)//奇数个负数
{
/*
* 除【绝对值最小的负数】之外的N-1个整数乘积最大
*/
$pick_out_index = $max_negative_index;
}
else//偶数个负数
{
if (0 < $amount_positive)
{//存在正数
/*
* 除【绝对值最小的正数】之外的N-1个整数乘积最大
*/
$pick_out_index = $min_positive_index;
}
else
{
/*
* 除【绝对值最大的负数】之外的N-1个整数乘积最大
* 乘积为负
*/
$pick_out_index = $min_negative_index;
}
}
}
/**
* 若需要计算N-1个元素的乘积
*/
$prod = 1;
for($i = 0; $i < $arr_len; $i++)
{
if ($i != $pick_out_index)
{
$prod *= $arr[$i];
}
}
return $prod;
}
}
几点说明：
- 这是我做《如何设计完备可靠的测试用例》培训用的一个代码示范，在github上开源的： https://github.com/qinjx/lotusphp/blo... ，会持续更新，敬请关注
- 我贴出来的测试用例只有“参数输入正确的正常流程”是100%做到了MECE（完全穷尽，彼此独立），“参数输入错误的异常流”还没做到MECE，极端情况的“白盒测试”就更谈不上MECE了，而且也没写测试方法体
只是个打酱油的
12 years, 5 months ago
Answers
php写代码太难受，我就不写了，主要要注意的几个点供参考：
1. 积可能会很大，要用大整数乘法。即使如此，大整数和一个int直接乘也可能会溢出，所以int也要先转换成一个大整数。php的整数底层是（有符号）long存的，32bit和64bit的最大数情况不一样，题目没有明确，保守点吧。
2. 会有0，两个以上的0结果直接返回0; 1个0和偶数个负数、无正数的情况也可以直接返回0。
3. 会有负数，要分别考虑奇数/偶数个负数的情况，分别考虑应该删掉 绝对值 最小的负数/正数。
4. 如果有偶数个负数的话，应当删除绝对值最大的负数。
后三个的逻辑（也许还有漏掉的情况）可以用暴力简化一下，把输入分成正数、零、负数三类，分别去掉1个零、最大的正数、最小的正数、最大的负数、最小的负数（最多去掉N个, N<=5）算出结果，然后再分别乘以那N个中的任意N-1个，比较一下结果，然后输出最大的就行了，这个效率也足够高。
想想还是写了个python的版本，我估计应该可以通过绝大部分测试了，比php写起来真是舒服太多了。
#!/usr/bin/python
def pop_min_max(l):
if len(l) == 0:
return []
max_item = max(l)
min_item = min(l)
l.remove(max_item)
if max_item == min_item:
return [max_item]
else:
l.remove(min_item)
return [max_item, min_item]
def findMaxProd(nums):
if not isinstance(nums, list) or len(nums) == 0:
raise Exception('bad input')
if len(nums) == 1:
return 1
positive = filter(lambda x: x > 0, nums)
negtive = filter(lambda x: x < 0, nums)
n_zero = len(nums) - len(positive) - len(negtive)
if n_zero > 1:
return 0
check_list = pop_min_max(positive) + pop_min_max(negtive)
if n_zero:
n_zero -= 1
check_list = [0] + check_list
pre_ans = reduce(lambda a, b: a * b, [0] * n_zero + positive + negtive, 1)
ans = []
for i in check_list:
ans.append(reduce(lambda a, b: a * b, filter(lambda x: x != i, check_list), pre_ans))
return max(ans)
print findMaxProd([2, 3, -1, -2, -3])
测试结果
根据题主的单元测试输出了一组测试用例，结果是有两组没通过（最后两组），其中一个是[10]这样的情况，我认为0个数相乘应该返回1（类似于x的0次方=1，这个见仁见智，不能算错吧），另一个是没有考虑数组中出现非int的情况。
由于python原生支持大整数运算，所以如果测试中出现超过int的数据，这代码应当也能顺便做对。
tests = [
(0, [0,0,0,0,0,0,0,-38,8,-28,86,-12,93,-3,3,-74,81,-57]),
(39200, [-1,-14,2,5,-14,0,10,-2]),
(62500, [-5,-2,0,-1,-25,-25,-10]),
(0, [-5,-21,-35,-64,-36,-72,-71,-64,-59,-83,-58,0,86,33,44,43,46,81,87]),
(0, [-50,-23,-60,-68,-72,-84,-16,-66,-50,-54,-74,0]),
(324900, [-10,-2,-5,-1,-57,-57,10]),
(-86490, [-1,-1024,-93,-5,-2,-93]),
(819200, [64,-5,4,-2,-10,64]),
(451250, [-5,-2,95,-10,95]),
(None, [10]),
(None, [-2,True,-5]),
]
for answer, arr in tests:
if answer != findMaxProd(arr):
print 'failed for:', str(arr)
运行测试输出
failed for: [10]
failed for: [-2, True, -5]
Kengo
answered 12 years, 5 months ago