次線性算法/找到最後的不同元素

Question

背景的情況下，你關心的，如果不是跳過它：

我記錄一些音頻今天，一個項目，做一次一個段落。如果我把這段文字搞亂了，我會重新編輯它，直到我把它弄對了，然後繼續下一段。當我將它們加載到電腦上時，我需要爲每個段落找到最後一個錄音。在不知道我爲特定段落錄製的錄音數量的情況下，我該怎麼做？ （當算法潛入你的日常生活中時，你不喜歡它嗎？）

在算法術語中，您有一個元素數組，其中每個元素後跟另一個相同類型的元素，或者完全不同元件。查找序列的每個最後一個元素（正確記錄的音頻剪輯）。

問題：

所以，你有對象的數組，其中有一個ID字段，其中每個ID是下面的列表中的每個元素。我想這是他們最後的ID的對象，比如說在ID的數組是這樣的：

aabbbbbccddddddddddddddeefffffffffggghhhhiiiijjklmnnnnoo 

顯然，如果字符串的長度爲n，有n個不同元素，它會帶你n個步驟來想辦法。我對通用算法更感興趣。我可以用二進制搜索類型算法來實現，但在不知道輸入的情況下，除了總元素的數量之外，我不知道它的運行時間。

此外，將知道不同ID的數量改變算法的運行時間？這對我來說是一個有趣的問題，我只是爲了滿足我的求知慾。

Answer 1

您應該可以查看第一個ID，然後對該ID結束的位置進行二分查找。這可以在O（log n）時間完成。

然後，您繼續前進到下一個元素，並重新進行二進制搜索以查找id序列結束的位置。

這產生複雜的算法O（米× log n）的其中Ñ是元件的數量和米不同元件的數量。

假設N/M（爲一個特定ID的元素的平均數量）大於爲log N你得到一個子線性算法。

如果N/M小於爲log N您正在搜索的ID序列線性結束的好。

（注意，這整個分析依賴於一個事實，即列表上的ID進行排序。通常排序需要時間成正比ñ×爲log N所以如果你需要對它們進行排序，你可以也一起去線性算法:-)

Answer 2

二進制搜索的運行時間與log（n）成正比。這意味着你添加的元素越多，增長越慢。更確切地說，問題規模的指數增長意味着執行時間的線性增長。換句話說，每次你把錄音的數量加倍時，你需要再聽一遍才能找到你想要的。

爲了做一個二進制搜索，你應該從你的記錄列表中間開始，找出你想要的記錄是在它之前還是之後，然後丟棄不包含它的一半。如果錄音是正確的段落（但您不知道它是好還是壞），則將其與後面的組合，並放棄之前的所有錄音。繼續消除一半（通過聽中間一個），直到你下降到1或2個錄音。

Answer 3

獲取數組中的第一個和最後一個元素並分析此範圍中的中間元素。如果找到新的id，則將最後一個元素放入堆棧（id及其到目前爲止找到的位置範圍）。否則，繼續在最低元素和中間元素之間的二進制搜索。當找到最後一個不同的元素時，彈出堆棧並繼續搜索。

時間複雜度爲O(m * log(n/m))，空間複雜度爲log(m)。其中m是不同值的數量。

Answer 4

「經典」二分查找的變體不是拆分整個空間，而是以幾何方式增長。也就是說，如果你所在的位置p，嘗試看看p +1，p +3，p +7，p +15，...，直到你找到一個間隔，在其中新標識會發生變化，您可以通過經典的二進制搜索將其拆分，或者甚至可以在最後一次已知的良好位置再次開始新的增長。

複雜性可能是一樣的人之前，也就是O（米 *登錄ñ），但是這可能是更適合您的問題，因爲同一ID的運行被認爲是相對較短（大約n/m）。