我不會深入探討我試圖解決的問題的細節，但它處理大字符串並涉及找到字符串中存在的重疊間隔。我只能使用其中一個重疊的間隔，所以我想將這些間隔分開並單獨分析。我想知道用什麼算法來儘可能有效地做到這一點。查找字符串重疊的高效算法
我必須強調，速度是至關重要的。我需要儘快分開時間間隔。我想到的算法是間隔樹，但我不確定這是否是我們能做的最好的。
區間樹可以在O（log n）時間查詢，n是區間數，構造需要O（nlog n）時間，但我想知道是否可以減少。
謝謝！
編輯：我知道問題是模糊的。我對這種混亂表示抱歉。我建議人們看看Aaron Huran的回答以及相同的評論。這應該有助於澄清更多事情。
嗯，昨天晚上我很無聊，所以我在Python中做了這個。它是不必要的遞歸（我只是讀了The Little Schemer，認爲遞歸現在非常整齊），但它解決了你的問題，並處理了我投擲它的所有輸入。
intervals = [(0,4), (5,13), (8,19), (10,12)]
def overlaps(x,y):
x1, x2 = x
y1, y2 = y
return (
(x1 <= y1 <= x2) or
(x1 <= y2 <= x2) or
(y1 <= x1 <= y2) or
(y1 <= x2 <= y2)
)
def find_overlaps(intervals, checklist=None, pending=None):
if not intervals:
return []
interval = intervals.pop()
if not checklist:
return find_overlaps(intervals, [interval], [interval])
check = checklist.pop()
if overlaps(interval, check):
pending = pending or []
checklist.append(check)
checklist.append(interval)
return pending + [interval] + find_overlaps(intervals, checklist)
else:
intervals.append(interval)
return find_overlaps(intervals, checklist)
使用這樣的：
>>> find_overlaps(intervals)
[(10, 12), (8, 19), (5, 13)]
注意，它返回所有重疊的間隔在其起點的順序相反。希望這是一個小問題。這只是因爲我在清單末尾使用了push()和pop()，而不是在開始時運行的insert(0)和pop(0)。
這並不完美，但它運行在線性時間。還要記住，實際字符串的大小根本不重要 - 運行時間是相對於間隔的數量而不是字符串的大小。
是的，我知道字符串的長度並不重要。我也在線性時間實現了類似的東西，但我希望我能做得更好。我認爲間隔樹可以讓我們降到O（log n），儘管我還沒有正確閱讀它們。 – efficiencyIsBliss 2010-07-09 16:18:32
什麼是'g'功能？你是否遺漏了某些東西，或者是某種內置的Python（我無法在互聯網上找到）？ – Lii 2016-01-24 21:12:36
我認爲這實際上是* O（n^2）*在重疊區間的數量，因爲在每次迭代中，您將所有先前找到的元素與新找到的元素一起復制到新列表中。另外，我相信你依靠預先分類的間隔，它是* O（n log n）*。 – Lii 2016-01-24 21:36:46
您正在計算兩個字符串之間的差異嗎？你想用什麼語言來做這件事？
更新： 沒有任何關於如何選擇使用哪個間隔的標準，有一個巨大的可能的解決方案。
一種方法是採取最低的起始數字，抓住它的結束。 抓住高於前一間隔結束的下一個起始號碼。獲取此間隔結束並重復。
因此，對於0-4,5-13,8-19,10-12, 您會得到：0-4,5-13並忽略其他。
我正在使用Java，但我不想計算兩個字符串之間的差異。我只有一個字符串，它內部定義了多個時間間隔。我需要使用這些間隔進行一些計算，但是我只能使用所有重疊間隔中的一個，這就是爲什麼我要將它們分開。 – efficiencyIsBliss 2010-07-09 03:58:01
@Dharmesh：你的意思是「其中定義了多個間隔」？你想解析一個數據格式嗎？如果是這樣，你能提供一些樣本輸入嗎？ – 2010-07-09 03:59:12
我附加了字符串間隔的分數，我需要得分最高的分數。所以，可能10-12間隔的分數最高，但如果我們使用上面描述的方法，我們會有O（n）的運行時間。 – efficiencyIsBliss 2010-07-09 13:36:06
免費的代碼版本你所說的「字符串中重疊的間隔」是什麼意思？ – 2010-07-09 03:53:07
字符串：「ThisIsATStringStringToShowWhatIMeanByIntervals」 間隔：0-4,5-13,8-19,10-12 這裏，間隔5-13,8-19和10-12重疊，所以我只能使用其中一個他們。 – efficiencyIsBliss 2010-07-09 04:00:53
間隔是否始終按起點排序？ – Triptych 2010-07-09 04:04:45