c++ - 我们如何找到给定子矩阵中不同元素的数量？

Question

已关闭。此问题不符合 Stack Overflow guidelines 。目前不接受答案。

---

要求提供代码的问题必须表现出对所解决问题的最低限度的了解。包括尝试的解决方案、为什么它们不起作用以及预期结果。另请参阅:Stack Overflow question checklist

已关闭 9 年前。

Improve this question

给定一个 N*N 矩阵，并对同一给定矩阵进行 Q 次查询。每个查询的形式为 x1,y1,x2,y2。我们必须找到分别由 (x1,y1) 和 (x2,y2) 定义为左上角和右下角的子矩阵中不同元素的数量。约束:N<=300Q<=10^5我使用简单的方法迭代每个查询的子矩阵。有没有更好的方法？

Answer 1

这取决于您可以预期的查询数量，以及您可以预期的相同查询的数量。

一种方法是“内存”查询，简单地存储每个查询和结果，并在进行更认真的工作之前进行查找。

一种更针对特定问题的方法(可能是您的老师所追求的)是为每个 (right,bottom)=(x,y) 计算 (0, 0, x, y) 的不同元素。然后用简单的集合论来处理每个查询。但进行原始计算非常耗时。

请记住添加对此答案的引用。