performance - 为多模式对象设计 DS

Question

衬衫种类繁多。品种基于图案、尺寸、颜色等参数。

假设你有所有类型的衬衫可用。现在有各种查询，例如：

Show all types of shirt having colour “red”.

Show all types of shirt having size “small” and pattern “checks” etc. etc.

那么，假设我们有“K”个不同的品种和 N 件衬衫，我们可以设计什么数据结构来存储以下数据，以最优化的方式回答上述查询？

我认为一个明显的解决方案是存储“K”个数据实例，根据每个品种进行分组。但这将非常节省空间。

牢记空间/时间界限，我们能做些什么更好？

Answer 1

如何存储K每个项目的指针，指示具有相同 K-th 品种的下一个项目。

然后对于每个查询，选择一个品种并枚举满足该品种的所有项目，检查它是否满足其他约束并显示它。因此，O(NK)为每个查询和O(1)添加一个新项目取一个，而空间为O(NK).

你的场景看起来就像一个数据库，你为什么不检查一下。