Finden Sie die Anzahl der Paare in einem Array, dessen Differenz K ist?

Question

Also im Grunde, was ich versuche Abfrage zu tun ist,

static int NumdiffExponential(int[] arr, int K) 
{ 
    return (from i in arr 
      from j in arr 
      where (j - i) == K 
      select 1).Count(); 
} 

außer in linearer Zeit, vorzugsweise mit einer einzigen LINQ und in eine Weise, die kompakten, gut lesbare und Mikro-optimal ist. Also, was ich herauskommen, ist der Versuch,

static int NumdiffLinear(int[] arr, int K) 
{ 
    var counters = 
     arr 
     .GroupBy(i => i) 
     .ToDictionary(g => g.Key, g => g.Count()); 
    return 
     counters 
     .Keys 
     .Aggregate(
      0, 
      (total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0) 
     ); 
} 

die als 0 herauskommen hält und ich kann nicht herausfinden, warum.

Lassen Sie mich erklären, wie ich denke, es funktioniert. Wenn wir arr={1,1,1,2,3,3,5} und K=2 haben, dann ist das counter wie

1->3, 2->1, 3->2, 5->1 

count = 0 lassen.

Ich nehme den Schlüssel 1 und sehen, dass 1-K=-1 kein Schlüssel in counter ist und daher count = 0 noch. Gleiches mit dem Schlüssel 2.

Für den Schlüssel 3 haben wir 3-K=1, die ein Schlüssel in counter ist. Es gibt 3 Vorkommen des Schlüssels 1 (dh counter[3]=1 und 2 Vorkommen des Schlüssels 2. Daher count = 3*2 = 6 wegen der Paare (1,3), (1,3), (1,3), (1,3), (1,3), (1,3), (1,3), die gebildet werden können

Mit der gleichen Logik wie oben, fügen wir eine weitere zu count wegen des Paares (3,5) Antwort ist count = 7.

alles falsch mit meinem Algorithmus oder die Umsetzung davon?

Answer 1

Sie können fix-up die Ihre Lösung wie folgt

public int NumdiffLinear(int[] arr, int K) 
     { 
      var dupsDictionary = 
       arr 
        .GroupBy(i => i) 
        .ToDictionary(g => g.Key, g => g.Count()); 


      return dupsDictionary.Keys.Aggregate(
       0, 
       (total, i) => 
        total + 
        dupsDictionary.Keys.Where(key => i - key == K) 
         .Sum(key => dupsDictionary[key]*dupsDictionary[i])); 
     } 

Answer 2

ersetzen

(total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0) 

von

(total, i) => total + counters[i] * (counters.ContainsKey(i-K) ? counters[i-K] : 0) 

Answer 3

lesbaren und viel kompakter:

static int NumdiffLinear(int[] arr, int K) 
{ 
    return arr.SelectMany(v => arr, (a, b) => new { a, b }) 
       .Where(s => s.b - s.a == K) 
       .Count(); 
} 

Hier ist ein linearer mit dem gleichen Prinzip:

static int NumdiffLinear(int[] arr, int K) 
{ 
    int n = 1; 
    return arr.Select(value => new { value, index = n++ }) //Get number and index 
       .SelectMany(indexValue => arr.Skip(indexValue.index), (a, b) => new { a = a.value, b }) //Project it with the next elements in the array 
       .Where(s => s.a - s.b == K) //Do the math 
       .Count(); 
} 

Answer 4

Sie statt subtrahieren hinzufügen sollten. Zum Beispiel wissen Sie, dass Sie key = 1 und K = 2 haben. dann müssen Sie prüfen ob key = (1+2) vorhanden ist oder nicht. In Ihrem O (n^2) Algorithmus überprüfen Sie J - I == K. Jetzt nehmen Sie an, Sie haben nur I und K. Einfache Mathematik nur tun J = K + I, wenn die Bedingung wahr wäre, dann sollte J existieren.

(total, i) => total + counters[i] * (counters.ContainsKey(K + i) ? counters[K + i] : 0)