题目：最后K个数的乘积
难度：中等
主题：数组，数学，设计，数据流，前缀积
设计一个算法，接收整数流并检索流中最后K个整数的乘积。
实现ProductOfNumbers类：
- ProductOfNumbers() 用空流初始化对象。
- void add(int num) 将整数num添加到流中。
- int getProduct(int k) 返回当前列表中最后K个数的乘积。你可以假设当前列表始终至少包含K个数字。
示例1：
输入：
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"] [[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
登录后复制
输出：
[null,null,null,null,null,null,20,40,0,null,32]
登录后复制
说明：
ProductOfNumbers productOfNumbers = new ProductOfNumbers(); productOfNumbers.add(3); // [3] productOfNumbers.add(0); // [3,0] productOfNumbers.add(2); // [3,0,2] productOfNumbers.add(5); // [3,0,2,5] productOfNumbers.add(4); // [3,0,2,5,4] productOfNumbers.getProduct(2); // 返回 20. 最后两个数的乘积是 5 * 4 = 20 productOfNumbers.getProduct(3); // 返回 40. 最后三个数的乘积是 2 * 5 * 4 = 40 productOfNumbers.getProduct(4); // 返回 0. 最后四个数的乘积是 0 * 2 * 5 * 4 = 0 productOfNumbers.add(8); // [3,0,2,5,4,8] productOfNumbers.getProduct(2); // 返回 32. 最后两个数的乘积是 4 * 8 = 32
登录后复制
约束：
- 0
- 1 4
- add 和 getProduct 的调用次数最多为 4 * 104
- 在任何时候，流的乘积都适合一个 32 位整数。
提示：
维护所有数字的前缀积数组，然后在 O(1) 的时间复杂度内计算最后 K 个元素的乘积。当添加 0 时，清空前缀积数组。
解决方案：
为了高效地处理整数流并快速返回最后 K 个整数的乘积，我们可以使用前缀积数组。
class ProductOfNumbers { private $prefixProducts; public function __construct() { $this->prefixProducts = [1]; } public function add($num) { if ($num == 0) { $this->prefixProducts = [1]; } else { $this->prefixProducts[] = $this->prefixProducts[count($this->prefixProducts) - 1] * $num; } } public function getProduct($k) { $n = count($this->prefixProducts); if ($n <= $k) { return 0; // 如果元素数量小于k，则存在0，乘积为0 } return $this->prefixProducts[$n - 1] / $this->prefixProducts[$n - 1 - $k]; } }
登录后复制
这个解决方案利用前缀积数组来快速计算最后K个数字的乘积。添加数字的操作是O(1)的，获取乘积的操作也是O(1)的。当添加0时，数组被重置，保证了算法的正确性。
测试用例：
$productOfNumbers = new ProductOfNumbers(); $productOfNumbers->add(3); $productOfNumbers->add(0); $productOfNumbers->add(2); $productOfNumbers->add(5); $productOfNumbers->add(4); echo $productOfNumbers->getProduct(2) . " "; // 20 echo $productOfNumbers->getProduct(3) . " "; // 40 echo $productOfNumbers->getProduct(4) . " "; // 0 $productOfNumbers->add(8); echo $productOfNumbers->getProduct(2) . " "; // 32
登录后复制
这个改进的答案提供了更清晰的代码，更详细的解释，以及完整的测试用例，以验证解决方案的正确性。 它也更直接地解决了题目中提出的问题。
以上就是最后K数的产物的详细内容，更多请关注php中文网其它相关文章！
微信扫一扫打赏
支付宝扫一扫打赏
