假设我正在使用 C# 开发 Excel 克隆。
我的网格表示如下：
private struct CellValue
{
private int column;
private int row;
private string text;
}
private List<CellValue> cellValues = new List<CellValue>();
每次用户添加文本时，我只需将其打包为 CellValue 并将其添加到 cellValues 中。给定一个 CellValue 类型，我可以在 O(1) 时间内确定它的行和列，这很棒。但是，给定一列和一行，我需要循环遍历整个 cellValues 来查找该列和行中的文本，这是非常慢的。另外，给定一个文本，我也需要循环遍历整个内容。是否有任何数据结构可以让我在 O(1) 时间内完成所有 3 个任务？
更新：
浏览了一些答案，我认为我没有找到我喜欢的答案。我可以吗：
- 不要保留超过 2 个 CellValue 副本，以避免同步它们。在 C 世界中，我会很好地使用指针。
- 行和列可以动态添加（与 Excel 不同）。
我会选择稀疏数组（链表的链表），以最小的存储空间提供最大的灵活性。
在此示例中，您有一个行链接列表，其中每个元素都指向该行中的单元格链接列表（您可以根据需要反转单元格和行）。
|
V
+-+ +---+ +---+
|1| -> |1.1| ----------> |1.3| -:
+-+ +---+ +---+
|
V
+-+ +---+
|7| ----------> |7.2| -:
+-+ +---+
|
=
每个行元素都有行号，每个单元格元素都有一个指向其行元素的指针，因此从单元格获取行号的时间复杂度为 O(1)。
类似地，每个单元格元素都有其列号，也使得 O(1) 复杂度。
没有简单的方法可以让 O(1) 立即查找给定行/列处的单元格，但是稀疏数组的速度是最快的，除非您为每个可能的单元格预先分配信息以便可以进行索引查找在数组上 - 这在存储方面会非常浪费。
您可以做的一件事是使一维非稀疏，例如使列成为主数组（而不是链接列表）并将它们限制为 1,000 - 这将使列查找建立索引（快速），然后在稀疏上进行搜索行。
我不认为你可以ever文本查找的复杂度为 O(1)，因为文本可以在多个单元格中重复（与行/列不同）。我仍然相信稀疏数组将是搜索文本的最快方法，除非您在另一个数组中维护所有文本值的排序索引（同样，这可以使其更快，但会占用大量内存）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
