3815. 设计拍卖系统

English Version

题目描述

请你设计一个拍卖系统，该系统可以实时管理来自多个用户的出价。

每个出价都与一个 userId（用户 ID）、一个 itemId（商品 ID）和一个 bidAmount（出价金额）相关联。

实现 AuctionSystem 类：

• AuctionSystem(): 初始化 AuctionSystem 对象。
• void addBid(int userId, int itemId, int bidAmount): 为 itemId 添加 userId 的一条新的出价，金额为 bidAmount。如果同一个 userId 已经对 itemId 出过价，则 用新的 bidAmount 替换 原有出价。
• void updateBid(int userId, int itemId, int newAmount): 将 userId 对 itemId 的已有出价更新为 newAmount。题目数据 保证 此出价 一定存在。
• void removeBid(int userId, int itemId): 移除 userId 对 itemId 的出价。题目数据  保证 此出价 一定存在。
• int getHighestBidder(int itemId): 返回对 itemId 出价最高的用户 userId。如果有多个用户的出价 相同且最高，返回 userId 较大的用户。如果该商品没有任何出价，则返回 -1。

示例 1：

AuctionSystem auctionSystem = new AuctionSystem(); // 初始化拍卖系统
auctionSystem.addBid(1, 7, 5); // 用户 1 对商品 7 出价 5
auctionSystem.addBid(2, 7, 6); // 用户 2 对商品 7 出价 6
auctionSystem.getHighestBidder(7); // 返回 2，因为用户 2 的出价最高
auctionSystem.updateBid(1, 7, 8); // 用户 1 更新对商品 7 的出价为 8
auctionSystem.getHighestBidder(7); // 返回 1，因为用户 1 的出价现在最高
auctionSystem.removeBid(2, 7); // 移除用户 2 对商品 7 的出价
auctionSystem.getHighestBidder(7); // 返回 1，因为用户 1 是当前最高出价者
auctionSystem.getHighestBidder(3); // 返回 -1，因为商品 3 没有任何出价

提示：

• 1 <= userId, itemId <= 5 * 104
• 1 <= bidAmount, newAmount <= 109
• 最多调用 5 * 104 次 addBid、updateBid、removeBid 和 getHighestBidder。
• 输入保证，对于 updateBid 和 removeBid 操作，给定的 userId 和 itemId 的出价一定有效。

解法

方法一：哈希表 + 有序集合

我们定义两个哈希表，其中 $\textit{items}$ 用于存储每个商品的所有出价信息，即 $\textit{items}[\textit{itemId}]$ 存储一个有序集合，集合中的每个元素为一个二元组 $(\textit{bidAmount}, \textit{userId})$，表示某个用户对该商品的出价金额。由于我们需要快速获取出价最高的用户，因此该有序集合需要按照出价金额从小到大排序，如果出价金额相同，则按照用户 ID 从小到大排序；另一个哈希表 $\textit{users}$ 用于存储每个用户对各个商品的出价信息，即 $\textit{users}[\textit{userId}][\textit{itemId}]$ 存储该用户对该商品的出价金额。

对于 addBid(userId, itemId, bidAmount) 操作，我们首先检查该用户是否已经对该商品出过价，如果是，则调用 removeBid(userId, itemId) 方法移除原有出价；然后将新的出价信息添加到 $\textit{users}$ 和 $\textit{items}$ 中。

对于 updateBid(userId, itemId, newAmount) 操作，我们首先从 $\textit{users}$ 中获取该用户对该商品的原有出价金额，然后在 $\textit{items}$ 中移除对应的二元组 $(\textit{oldAmount}, \textit{userId})$，再将新的出价信息添加到 $\textit{items}$ 中，并更新 $\textit{users}$ 中的出价金额。

对于 removeBid(userId, itemId) 操作，我们首先从 $\textit{users}$ 中获取该用户对该商品的原有出价金额，然后在 $\textit{items}$ 中移除对应的二元组 $(\textit{oldAmount}, \textit{userId})$，最后从 $\textit{users}$ 中删除该用户对该商品的出价信息。

对于 getHighestBidder(itemId) 操作，我们首先检查 $\textit{items}[\textit{itemId}]$ 是否为空，如果为空则返回 -1；否则返回该有序集合中最后一个元素的用户 ID，即出价最高的用户。

时间复杂度方面，每次操作的时间复杂度均为 $O(\log m)$，其中 $m$ 为当前商品的出价数量。空间复杂度为 $O(n)$，其中 $n$ 为所有出价的总数量。

Python3

class AuctionSystem:

    def __init__(self):
        self.items = defaultdict(SortedList)
        self.users = {}

    def addBid(self, userId: int, itemId: int, bidAmount: int) -> None:
        if userId not in self.users:
            self.users[userId] = {}
        if itemId in self.users[userId]:
            self.removeBid(userId, itemId)
        self.users[userId][itemId] = bidAmount
        self.items[itemId].add((bidAmount, userId))

    def updateBid(self, userId: int, itemId: int, newAmount: int) -> None:
        oldAmount = self.users[userId][itemId]
        self.items[itemId].remove((oldAmount, userId))
        self.items[itemId].add((newAmount, userId))
        self.users[userId][itemId] = newAmount

    def removeBid(self, userId: int, itemId: int) -> None:
        oldAmount = self.users[userId][itemId]
        self.items[itemId].remove((oldAmount, userId))
        self.users[userId].pop(itemId)

    def getHighestBidder(self, itemId: int) -> int:
        ls = self.items[itemId]
        return -1 if not ls else ls[-1][1]


# Your AuctionSystem object will be instantiated and called as such:
# obj = AuctionSystem()
# obj.addBid(userId,itemId,bidAmount)
# obj.updateBid(userId,itemId,newAmount)
# obj.removeBid(userId,itemId)
# param_4 = obj.getHighestBidder(itemId)

Java

class AuctionSystem {
    private final Map<Integer, TreeSet<int[]>> items = new HashMap<>();
    private final Map<Integer, Map<Integer, Integer>> users = new HashMap<>();

    public AuctionSystem() {
    }

    public void addBid(int userId, int itemId, int bidAmount) {
        users.computeIfAbsent(userId, k -> new HashMap<>());

        if (users.get(userId).containsKey(itemId)) {
            removeBid(userId, itemId);
        }

        users.get(userId).put(itemId, bidAmount);

        items.computeIfAbsent(itemId, k -> new TreeSet<>(
            (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1])
        ));

        items.get(itemId).add(new int[]{bidAmount, userId});
    }

    public void updateBid(int userId, int itemId, int newAmount) {
        int oldAmount = users.get(userId).get(itemId);
        TreeSet<int[]> set = items.get(itemId);

        set.remove(new int[]{oldAmount, userId});
        set.add(new int[]{newAmount, userId});

        users.get(userId).put(itemId, newAmount);
    }

    public void removeBid(int userId, int itemId) {
        int oldAmount = users.get(userId).get(itemId);
        TreeSet<int[]> set = items.get(itemId);

        set.remove(new int[]{oldAmount, userId});
        users.get(userId).remove(itemId);
    }

    public int getHighestBidder(int itemId) {
        TreeSet<int[]> set = items.get(itemId);
        if (set == null || set.isEmpty()) {
            return -1;
        }
        return set.last()[1];
    }
}

/**
 * Your AuctionSystem object will be instantiated and called as such:
 * AuctionSystem obj = new AuctionSystem();
 * obj.addBid(userId,itemId,bidAmount);
 * obj.updateBid(userId,itemId,newAmount);
 * obj.removeBid(userId,itemId);
 * int param_4 = obj.getHighestBidder(itemId);
 */

C++

class AuctionSystem {
    unordered_map<int, set<pair<int, int>>> items;
    unordered_map<int, unordered_map<int, int>> users;

public:
    AuctionSystem() {
    }

    void addBid(int userId, int itemId, int bidAmount) {
        if (users[userId].count(itemId)) {
            removeBid(userId, itemId);
        }
        users[userId][itemId] = bidAmount;
        items[itemId].insert({bidAmount, userId});
    }

    void updateBid(int userId, int itemId, int newAmount) {
        int oldAmount = users[userId][itemId];
        auto& s = items[itemId];
        s.erase({oldAmount, userId});
        s.insert({newAmount, userId});
        users[userId][itemId] = newAmount;
    }

    void removeBid(int userId, int itemId) {
        int oldAmount = users[userId][itemId];
        auto& s = items[itemId];
        s.erase({oldAmount, userId});
        users[userId].erase(itemId);
    }

    int getHighestBidder(int itemId) {
        auto it = items.find(itemId);
        if (it == items.end() || it->second.empty()) {
            return -1;
        }
        return it->second.rbegin()->second;
    }
};

/**
 * Your AuctionSystem object will be instantiated and called as such:
 * AuctionSystem* obj = new AuctionSystem();
 * obj->addBid(userId,itemId,bidAmount);
 * obj->updateBid(userId,itemId,newAmount);
 * obj->removeBid(userId,itemId);
 * int param_4 = obj->getHighestBidder(itemId);
 */

Go