How to Compute the Product of Last K elements in Array using the

  • 时间：2020-09-10 13:27:27
  • 分类：网络文摘
  • 阅读：151 次

Implement the class ProductOfNumbers that supports two methods:
1. add(int num)
Adds the number num to the back of the current list of numbers.
2. getProduct(int k)
Returns the product of the last k numbers in the current list.
You can assume that always the current list has at least k numbers.

At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example:
Input

1
2

["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output

1

[null,null,null,null,null,null,20,40,0,null,32]
[null,null,null,null,null,null,20,40,0,null,32]

Explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32 
 
Hints:
Keep all prefix products of numbers in an array, then calculate the product of last K elements in O(1) complexity.
Hide Hint 2
When a zero number is added, clean the array of prefix products.
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); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32 

Hints:
Keep all prefix products of numbers in an array, then calculate the product of last K elements in O(1) complexity.
Hide Hint 2
When a zero number is added, clean the array of prefix products.

Constraints:
There will be at most 40000 operations considering both add and getProduct.
0 <= num <= 100
1 <= k <= 40000

Bruteforce Algorithm to Compute the Last K Products of Array

Probably the easiest solution is to apply the bruteforce algorithm. To add a number, we use the append method of the list. And to get the product of the Last K elements, we can use array slicing and the reduce function from functools.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

from functools import reduce
 
class ProductOfNumbers:
    def __init__(self):
        self.data = []
 
    def add(self, num: int) -> None:
        self.data.append(num)
 
    def getProduct(self, k: int) -> int:
        return reduce((lambda x, y: x * y), self.data[-k:], 1)
 
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
from functools import reduce

class ProductOfNumbers:
    def __init__(self):
        self.data = []

    def add(self, num: int) -> None:
        self.data.append(num)

    def getProduct(self, k: int) -> int:
        return reduce((lambda x, y: x * y), self.data[-k:], 1)

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

The Python code is inefficient for large data sets. The above solution may time out while the following equivalent C++ implementation may not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class ProductOfNumbers {
public:
    ProductOfNumbers() {
        
    }
    
    void add(int num) {
        data.push_back(num);
    }
    
    int getProduct(int k) {
        int s = 1;
        for (int i = 0; i < k; ++ i) {
            s *= data[data.size() - i - 1];
        }
        return s;
    }
private:
    vector<int> data;
};
 
/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
*/
class ProductOfNumbers {
public:
    ProductOfNumbers() {
        
    }
    
    void add(int num) {
        data.push_back(num);
    }
    
    int getProduct(int k) {
        int s = 1;
        for (int i = 0; i < k; ++ i) {
            s *= data[data.size() - i - 1];
        }
        return s;
    }
private:
    vector<int> data;
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
*/

We may use the std::accumulate() to rewrite the product part:

1
2
3

return std::accumulate(end(data) - k - 1, end(data), 1, [](auto &a, &b) {
   return a * b;
}); 
return std::accumulate(end(data) - k - 1, end(data), 1, [](auto &a, &b) {
   return a * b;
});

The bruteforce runs at O(1) time in add() and O(N) time in getProduct().

Compute the Last K Products of An Array using Prefix Products

Since all the inputs are integers, we can store the prefix product (the product of all the present numbers) while we add a new number to the list.

When we have a zero, we need to clear the array. The result would be the division between the last prefix sum and the prefix sum at [-k] position

See Python solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class ProductOfNumbers
    def __init__(self):
        self.data = [1]
 
    def add(self, num: int) -> None:
        if num == 0:
            self.data = [1]
        else:
            self.data.append(num * self.data[-1])
 
    def getProduct(self, k: int) -> int:
        if k >= len(self.data):
            return 0
        return self.data[-1] // self.data[ - k - 1]
 
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
class ProductOfNumbers
    def __init__(self):
        self.data = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.data = [1]
        else:
            self.data.append(num * self.data[-1])

    def getProduct(self, k: int) -> int:
        if k >= len(self.data):
            return 0
        return self.data[-1] // self.data[ - k - 1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

And the C++ solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class ProductOfNumbers {
public:
    ProductOfNumbers() {
    }
    
    void add(int num) {
        if (num > 0) {
            data.push_back(num * data.back());
        } else {
            data = {1};
        }
    }
    
    int getProduct(int k) {
        return k < data.size() ? data.back() / data[data.size() - k - 1] : 0;
    }
private:
    vector<int> data{1};
};
 
/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */
class ProductOfNumbers {
public:
    ProductOfNumbers() {
    }
    
    void add(int num) {
        if (num > 0) {
            data.push_back(num * data.back());
        } else {
            data = {1};
        }
    }
    
    int getProduct(int k) {
        return k < data.size() ? data.back() / data[data.size() - k - 1] : 0;
    }
private:
    vector<int> data{1};
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

The prefix product algorithm brings the complexity of the getProduct() method down to O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
6 Best Fashion Bloggers for Style Inspiration　 The Strategy You Need to Write Better Blog Posts Than Your Compe　 How to Improve Your Blog’s Bounce Rate (and Why You Should)　 Does Your SME Have A Disaster Recovery Plan?　 7 Best SEO Trends Gaining Popularity In 2019　 How To Choose The Best Hosting Service For A WordPress Website　 An Idiot’s Guide to Email Automation for Bloggers　 Checklist for Choosing a Perfect WordPress Blog Theme　 15 Mindset Hacks to Avoid Blogging Failure　 Can Retailers Refuse Refunds Using POS Software?　
评论列表
添加评论