Anzahl der Paare von Zahlen mit einer Differenz von mindestens K

Question

Gegeben n, die Anzahl der Begriffe im Array und k, eine positive Zahl und ein Array arr[], wird erwartet, dass die Anzahl der Paare in der Anordnung, so dass ihre Differenz ist mindestens k.
EX:
INPUT

7 2 
2 4 3 5 6 1 7 

OUTPUT

15 

So war mein Ansatz:

int main() 
{ 
    long long int n,k; 
    scanf("%lld %lld",&n,&k); 
    long long int a=0,arr[n]; 
    while(a<n) 
    { 
    scanf("%lld",&arr[a]); 
    a++; 
    } 
    quicksort(arr,0,n-1);//sorting the array 
    long long int i=n-1,j=0,ans=0;//two-pointer method 
    while(i>0) 
    { 
    if(arr[i] - arr[j] >= k && j < i) 
    { 
     ans ++; 
     j++; 
    } 
    else 
    { 
     i--; 
     j = 0; 
    } 
    } 
    printf("%lld",ans); 
    return 0; 
} 

Aber die Lösung übersteigt für größere Testfälle Frist. Irgendwelche Verbesserungen möglich?

Answer 1

Sie können die binäre Suche in diesem Problem verwenden. Nach dem Sortieren des Arrays können Sie Paare mit einer Differenz von mehr als K für jedes Element x von binary searching für K+x finden. Nach dem Finden des Index i, wo die Elemente nach dem alle Wert gleich oder mehr als K+x haben, können Sie das Problem leicht lösen.

total = 0 
sort(arr) 
for each x in arr: 
    i = lower_bound(K+x) 
    total += arr.size - i 

Answer 2

Wie es ist, Sie immer nur erhöhen die Antwort von 1. Nachdem das Array sortiert wird, würde ich zwei Indexvariablen von unten laufen. Erhöhen Sie den oberen Index, bis die Differenz der Elemente> = k ist. Dann weiß ich, dass der Unterschied mit allen folgenden Elementen auch> = k ist, also kann die verbleibende Länge des Arrays zur Antwort hinzugefügt werden. Erhöhen Sie dann den unteren Index und fügen Sie die Länge des verbleibenden Arrays hinzu, bis der Unterschied < k ist. Der untere Index jagt also den oberen Index entlang des Arrays, nur ein einziger Durchlauf ist erforderlich.

Answer 3

Verbesserungen können in While-Schleife vorgenommen werden. Sie suchen nach allen Elementen, die die angegebene Bedingung erfüllen. Wir können die Sortierung ausnutzen, indem wir nur nach einem Element suchen (zB b, Da arr [i] + k < = b), die nachfolgenden Elemente würden dann immer die Bedingung erfüllen und somit die durchgeführten Suchen reduzieren.

int n,k; 
cin>>n>>k; 
std::vector<int> v(n,0); 

for(int i = 0;i < n;++i) 
    cin>>v[i]; 

sort(v.begin(),v.end()); 

std::vector<int> ::iterator it; 
int result = 0; 

for(int i = 0;i < n; ++i){ 
    int a = v[i]; 
    it = lower_bound(v.begin(),v.end(),a+k); // find the element that satisfies a + k <= b 
    if(it != v.end()) 
     result += n - (it - v.begin()); // number of elements which are more than b 
} 

cout<<result<<"\n";