逐一存储项目并返回按计数排序的 n 个项目的最佳算法和数据结构是什么？

Question

在一次采访中，我被要求实现一个在线商店，该商店具有一个购买函数，该函数接收已购买的商品 ID，以及一个返回最多 n 个购买商品的函数。 如果我使用以项目 id 作为键并以计数作为值的哈希表，我可以在 o(1) 处更新计数器，但是当我需要最常购买的项目列表时，我必须对其进行排序并修剪结果。 有更好的办法吗？

Answer 1

根据购买数量，通过使用两个数据结构使其成为 O（购买数量）可能会很有趣（或没有）：

• 按购买数量计算的一组产品 ID。因此它可能是一个数组，其中索引是该计数，条目是一组已售出多次的产品 ID。
每个产品 ID 的计数：您已计划使用。

这是 JavaScript 类中的实现和示例运行：

class Store {
    constructor() {
        // Dynamic array (vector) of sets of product ids.
        //    Index 0 is not used, so we already place a null there:
        this.productsPerCount = [null];
        // HashSet keyed by product ids and counts as corresponding values:
        this.countPerProduct = new Map();
    }
    purchase(id) {
        let count = this.countPerProduct.get(id) ?? 0; // default to 0 if not found
        if (count > 0) {
            this.productsPerCount[count].delete(id); // Remove product from set
        }
        count++;
        this.countPerProduct.set(id, count);
        if (count >= this.productsPerCount.length) {
            this.productsPerCount.push(new Set); // Extend array to needed size
        }
        this.productsPerCount[count].add(id); // Add product to set
    }
    mostPurchased(n) {
        const list = [];
        if (n == 0) return list; 
        // By decreasing count...
        for (let count = this.productsPerCount.length - 1; count > 0; count--) {
            for (let id of this.productsPerCount[count]) { // All products in this set
                list.push(id);
                if (list.length == n) return list;
            }
        }
        // Not enough purchases, but let's return what we have:
        return list;
    }
}

// Example run
const store = new Store();
for (const id of [10,20,30,40,20,30,20,50,20]) {
    store.purchase(id);
}
console.log(...store.mostPurchased(3)); // 20 30 10