最后K数的产物-php教程-PHP中文网

最后K数的产物

花韻仙語

发布： 2025-02-15 22:42:27

原创

302人浏览过

最后k数的产物

题目：最后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 * 10⁴
在任何时候，流的乘积都适合一个 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) . "\n"; // 20
echo $productOfNumbers->getProduct(3) . "\n"; // 40
echo $productOfNumbers->getProduct(4) . "\n"; // 0
$productOfNumbers->add(8);
echo $productOfNumbers->getProduct(2) . "\n"; // 32

登录后复制

这个改进的答案提供了更清晰的代码，更详细的解释，以及完整的测试用例，以验证解决方案的正确性。它也更直接地解决了题目中提出的问题。

以上就是最后K数的产物的详细内容，更多请关注php中文网其它相关文章！