Mehr speichereffizienter Algorithmus zum Auffinden von Überlappungen in Bereichen

Question

In Frage this enthielt die Antwort einen Algorithmus, um eine Überlappung einer Liste von Bereichen in einem bestimmten Bereich zu finden. Aber in meiner Situation habe ich eine Liste von n Ganzzahlen, die bei der Gruppierung in n^2 Paare Bereiche bilden. Zum Beispiel, wenn wir array[i] und array[j] aus dem Integer-Array nehmen, (array[i]-array[j],array[i]+array[j]) einen Bereich machen. Aber um den vorgeschlagenen Algorithmus zu implementieren, ist die Lösung von O(n^2) Speicherkomplexität. Kann es (hinsichtlich des Gedächtnisses) weiter optimiert werden?

Beispiel: Ich habe einen größeren Bereich (l,r), und ich habe, wie viele Zahlen in (l,r) liegen zu finden in mindestens einem der in der Liste der ranges.For Beispiel die gegebene Ganzzahl-Array {1,2,3} ist. So sind alle möglichen Bereiche (2-1,1+2), (3-1,1+3), (3-2,3+2). Angenommen (l,r) ist (2,7). Dann seit (2,5) in mindestens einem von ihnen 4 gibt es die Antwort.

Answer 1

Beginnen Sie mit der Sortierung des Arrays (wenn es nicht bereits sortiert ist). Beachten Sie, dass nur die Bereiche in Frage kommen, in denen j == i-1 gilt.

zu verstehen, warum die folgende Array betrachten:

{2,3,5,8} 

Dann werden die möglichen Bereiche sind:

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) 

Beachten Sie, dass die Bereiche für j < i-1 sind immer streng Teilmengen des Bereichs, in dem j == i-1, so dass diejenigen, Bereiche müssen nicht berücksichtigt werden. Sie müssen also nur O (n) Bereiche berücksichtigen.