What pattern does 'Apply Discount Every n Orders' follow?

It follows an array scanning plus hash lookup pattern, using hash maps for price retrieval and counting orders to apply periodic discounts.

How do I handle the discount application correctly?

Maintain a customer count and apply the discount only when the count is a multiple of n, multiplying the subtotal by (100 - discount)/100.

Is it efficient to scan products array for each getBill call?

No, using a hash map for product prices ensures O(1) lookup per item, making each getBill call efficient.

Can amount or product arrays contain duplicate items?

No, each product array per order has unique items, so duplicate handling is unnecessary.

What precision is expected for the final bill?

Answers within 10^-5 of the actual value are accepted, so maintain sufficient floating-point precision during calculations.

#1357

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

每隔 n 个顾客打折

Name: Interview AiBox
Availability: InStock
Rating: 4.9 (10000 reviews)

超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。超市里有一些商品，第 i 种商品为 products[i] 且每件单品的价格为 prices[i] 。结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount （也就是如果原本账单为…

数组哈希表设计

题目描述

超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。

超市里有一些商品，第 i 种商品为 products[i] 且每件单品的价格为 prices[i] 。

结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount （也就是如果原本账单为 x ，那么实际金额会变成 x - (discount * x) / 100 ），然后系统会重新开始计数。

顾客会购买一些商品， product[i] 是顾客购买的第 i 种商品， amount[i] 是对应的购买该种商品的数目。

请你实现 Cashier 类：

Cashier(int n, int discount, int[] products, int[] prices) 初始化实例对象，参数分别为打折频率 n ，折扣大小 discount ，超市里的商品列表 products 和它们的价格 prices 。
double getBill(int[] product, int[] amount) 返回账单的实际金额（如果有打折，请返回打折后的结果）。返回结果与标准答案误差在 10^-5 以内都视为正确结果。

示例 1：

输入
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
输出
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
解释
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]);                        // 返回 500.0, 账单金额为 = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]);                      // 返回 4000.0
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    // 返回 800.0 ，账单原本为 1600.0 ，但由于该顾客是第三位顾客，他将得到 50% 的折扣，所以实际金额为 1600 - 1600 * (50 / 100) = 800 。
cashier.getBill([4],[10]);                           // 返回 4000.0
cashier.getBill([7,3],[10,10]);                      // 返回 4000.0
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // 返回 7350.0 ，账单原本为 14700.0 ，但由于系统计数再次达到三，该顾客将得到 50% 的折扣，实际金额为 7350.0 。
cashier.getBill([2,3,5],[5,3,2]);                    // 返回 2500.0

提示：

1 <= n <= 10^4
0 <= discount <= 100
1 <= products.length <= 200
1 <= products[i] <= 200
products 列表中不会有重复的元素。
prices.length == products.length
1 <= prices[i] <= 1000
1 <= product.length <= products.length
product[i] 在 products 出现过。
amount.length == product.length
1 <= amount[i] <= 1000
最多有 1000 次对 getBill 函数的调用。
返回结果与标准答案误差在 10^-5 以内都视为正确结果。

lightbulb

解题思路

方法一：哈希表 + 模拟

用哈希表 $d$ 存储商品编号和价格，然后遍历商品编号和数量，计算总价，再根据折扣计算折扣后的价格。

初始化的时间复杂度为 $O(n)$ ，其中 $n$ 为商品的数量。getBill 函数的时间复杂度为 $O(m)$ ，其中 $m$ 为购买商品的数量。空间复杂度为 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Cashier:
    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
        self.i = 0
        self.n = n
        self.discount = discount
        self.d = {product: price for product, price in zip(products, prices)}

    def getBill(self, product: List[int], amount: List[int]) -> float:
        self.i += 1
        discount = self.discount if self.i % self.n == 0 else 0
        ans = 0
        for p, a in zip(product, amount):
            x = self.d[p] * a
            ans += x - (discount * x) / 100
        return ans


# Your Cashier object will be instantiated and called as such:
# obj = Cashier(n, discount, products, prices)
# param_1 = obj.getBill(product,amount)

speed

复杂度分析

指标	值
时间	complexity is O(k) per getBill call, where k is the number of products in the order, due to array iteration and hash lookups. Space complexity is O(m) for the hash map storing m product prices.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if your hash map avoids repeated array scans for price lookups.
question_mark
Make sure discount is applied only on every nth customer and tracked properly.
question_mark
Consider edge cases when amount arrays are empty or contain maximum quantities.

warning

常见陷阱

外企场景

error
Forgetting to increment the customer counter, causing discounts to be misapplied.
error
Incorrectly mapping product IDs to prices leading to wrong subtotal calculation.
error
Using nested loops over products for each getBill call, causing unnecessary time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Vary discount frequency, e.g., every mth customer, to test counter logic.
arrow_right_alt
Use floating-point prices or discounts to examine precision handling in subtotal computation.
arrow_right_alt
Allow multiple discounts for different customer groups, requiring separate counters and logic.

help

常见问题

外企场景

继续练习

#1146 快照数组 #1656 设计有序流 #911 在线选举