arrays - 次线性算法/找到最后一个不同的元素

Question

背景，如果你关心的话，如果不关心就跳过:

我今天正在为一个项目录制一些音频，一次录制一个段落。如果我把这一段搞砸了，我会重写直到我把它弄好，然后再继续下一段。当我将它们加载到计算机上时，我需要找到每个段落的最后录音。在不知道我为特定段落制作的录音数量的情况下，我该如何处理？ (当算法潜入您的日常生活时，您不喜欢它吗？)

在算法术语中，您有一个元素数组，其中每个元素后跟另一个相同类型的元素，或者一个完全不同的元素。找到序列的每个最后一个元素(正确录制的音频剪辑)。

问题:

所以你有一个对象数组，其中每个元素都有一个 id 字段，其中每个 id 都在以下列表中。我想要最后一个 ID 的对象，在这样的 ID 数组中说:

aabbbbbccddddddddddddddeefffffffffggghhhhiiiijjklmnnnnoo

显然，如果字符串的长度为 n 且有 n 个不同的元素，则需要 n 步才能算出。我对通用算法更感兴趣。我可以用二进制搜索类型的算法来做到这一点，但我不知道它的运行时间，因为除了总元素数之外，我不知道输入的情况。

此外，知道不同 ID 的数量会改变算法的运行时间吗？这对我来说是一个有趣的问题，我提出这个问题只是为了满足我的求知欲。

Answer 1

您应该能够查看第一个 id，并对该 id 结束的位置进行二进制搜索。这可以在 O(log n) 时间内完成。

然后您前进到下一个元素，并重新进行二进制搜索以查找该 id 序列的结束位置。

这会产生一个复杂度为 O(m × log n) 的算法，其中 n 是元素的数量，m 是不同元素的数量元素。

假设 n/m(特定 id 的平均元素数)大于 log n，您将得到一个次线性算法。

如果 n/m 小于 log n，您最好线性搜索 id 序列的结尾。

(请注意，整个分析取决于列表是根据 ID 排序的事实。排序通常花费的时间与 n × log n 成正比，因此如果您需要对它们进行排序，您可以以及使用线性算法:-)