正如我在項目中遇到的那樣，這本身不是一個采訪問題，但我認為這可能是一個不錯的干預問題。您有N對間隔，例如整數。您需要確定在O（N）時間內彼此重疊的所有間隔。例如，如果您有{1，3} {12，14} {2，4} {13，15} {5，10}答案是{1、3}，{12、14}，{2、4}，{13、15}。請注意，您無需對其進行分組，因此結果可以按示例中的任何順序排列。我只是花了O（N）的時間，因為KMP算法將O（N）用于字符串搜索。：D我想到的最好的東西是我現在在項目中使用的是O（N ^ 2）。是的，蠻力很可悲，但是沒有人抱怨，所以我不會重構它。：P不過，我很好奇，如果一個更大的頭腦有一個更優雅的解決方案。
3 回答
千萬里不及你
TA貢獻1784條經驗 獲得超9個贊
將間隔的端點放入數組中，將其標記為起點或終點。如果間隔是封閉的，則通過將端點放在起點之前來打破平局來對它們進行排序，如果間隔是半開放的，則將它們放在相反的位置。
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
然后遍歷該列表，跟蹤我們處于多少間隔（這等于已處理的起點數減去終點數）。每當我們已經處于一個間隔中而到達起點時，這意味著我們必須具有重疊的間隔。
1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
^ ^
overlap overlap
通過在端點旁邊存儲數據并跟蹤我們所處的間隔，我們可以找到哪些間隔與哪些間隔重疊。
這是一個O（N logN）解決方案，其中排序是主要因素。
慕的地8271018
TA貢獻1796條經驗 獲得超4個贊
在線間隔問題的標準方法是根據起點對它們進行排序，然后從頭到尾走動。O(n*logn)（O(n)如果已經排序）
end = 0;
for (current in intervals) {
if current.start < end {
// there's an intersection!
// 'current' intersects with some interval before it
...
}
end = max(end, current.end)
}
添加回答
舉報
0/150
提交
取消