用於查找範圍重疊的更高效的內存算法

在this問題中，答案包括一個算法來查找給定範圍內範圍列表的重疊。但在我的情況下，我有一個n整數列表，其中當分組爲n^2對形成範圍。例如，如果我們從整數數組中取array[i]和array[j]，則可以使用(array[i]-array[j],array[i]+array[j])作爲範圍。但爲了實現所提出的算法，解決方案的內存複雜度爲O(n^2)。它可以進一步優化（內存方面）嗎？用於查找範圍重疊的更高效的內存算法

實施例：我有一個較大的範圍(l,r)，我必須找到多少整數在(l,r)在於ranges.For示例的列表中的至少任一個，給定的整數數組是{1,2,3}。所以所有可能的範圍是(2-1,1+2), (3-1,1+3), (3-2,3+2)。假設(l,r)是(2,7)。那麼因爲(2,5)至少存在其中之一4就是答案。

來源

2017-02-04 yobro97

@ user3386109 .....我有更大的範圍'（l，r）'，我必須找出（l，r）中有多少個整數位於至少任何一個範圍列表中。範圍列表可以按照問題描述的方式從給定的整數數組中計算。 – yobro97

@ user3386109 ....例如，給定的整數數組是「{1,2,3}」。所以所有可能的範圍是（2-1,1 + 2），（3-1,1 + 3），（3-2,3 + 2）'。假設'（l，r）'是'（2,7）'。那麼因爲其中至少有一個「（2,5）」存在，所以'4'就是答案。 – yobro97

從排序數組開始（如果它尚未排序）。然後請注意，唯一值得考慮的範圍是那些j == i-1。

要理解爲什麼要考慮以下數組：

{2,3,5,8}

然後可能的範圍是：

i=3 j=2 ==> (8-5,8+5) = (3,13) 
i=3 j=1 ==> (8-3,8+3) = (5,11) 
i=3 j=0 ==> (8-2,8+2) = (6,10) 

i=2 j=1 ==> (5-3,5+3) = (2,8) 
i=2 j=0 ==> (5-2,5+2) = (3,7) 

i=1 j=0 ==> (3-2,3+2) = (1,5)

注意，對於j < i-1範圍總是在那裏j == i-1範圍的嚴格的子集，所以這些範圍不需要考慮。所以你只需要考慮O（n）範圍。

來源

2017-02-04 06:54:56 user3386109

謝謝....這是一個簡單而偉大的見解...... :) – yobro97

用於查找範圍重疊的更高效的內存算法

回答

相關問題