无需读取每个元素即可从数据集中搜索数据

Question

我刚刚开始学习算法和数据结构，我遇到了一个有趣的问题。

我需要一些帮助来解决这个问题。

有一组数据给了我。在数据集中是字符和与它们中的每一个相关联的数字。我必须计算与每个当前字符相关的最大数字的总和。该列表不是按字符排序的，但是每个字符的组被重复，并且在数据集中没有该字符的其他实例。

此外，与数据集中的每个字符相关联的最大数字总是出现在数据集中该字符的最大引用位置。我们知道整个数据集的长度，我们可以通过指定与该数据集关联的行号来检索数据。

例如。

C-7  
C-9  
C-12  
D-1  
D-8 
A-3  
M-67  
M-78  
M-90  
M-91  
M-92   
K-4  
K-7  
K-10  
L-13  
length=15  
get(3)= D-1(stores in class with character D and value 1)  

以上问题的答案应该是13+10+92+3+8+12，因为它们分别是与L,K,M,A,D,C相关的最高数字。

当然，最简单的解决方案是遍历所有元素，但最有效的算法是什么(读取小于数据集长度的数据集)？

Answer 1

由于您不能确定关键字是什么，因此您必须逐一查看它们。

为了便于操作，我会遍历数据集并检查索引i处的键是否等于i+1处的索引，如果不相等，则意味着您有一个局部最大值。

然后，如果没有该键的现有key:value对，则将该值存储到散列或字典中；如果存在，则检查现有值是否小于当前值，如果为true，则覆盖该值。

Answer 2

虽然你可以使用统计数据乐观地跳过一些条目-比如你读的是A1，但你跳过了5个条目你读的是A 10 - good。你又跳过了5，B3，所以你需要返回并阅读中间的内容。

但在现实中它是行不通的。不是在文本上。

因为IO是以块为单位发生的。数据通常存储在8k左右的区块中。因此，这是最小的读取大小(即使您的编程语言可以提供其他大小的读取，它们最终也会被转换为读取块并对其进行缓冲)。

你是如何找到下一行的？你会一直读直到你找到一个\n..。

因此，您不会保存此类数据的任何内容。如果您有更大的记录(几个KB，如文件)和一个索引，情况就不同了。但建立该索引将需要至少读取所有内容一次。

因此，如图所示，最快的方法可能是线性扫描整个数据一次。