Optimisation de cet algorithme C# (Différence K)

Question

C'est le problème que je suis la résolution (c'est un exemple de problème, pas un vrai problème):

nombres donnés N, [N < = 10^5] nous besoin de compter les paires totales de nombres qui ont une différence de K. [K> 0 et K < 1E9]

Format d'entrée: première ligne contient N & K (nombres entiers). La deuxième ligne contient N numéros de l'ensemble. Tous les N nombres sont assurés d'être distincts. Format de sortie: Un entier dire le nbre de paires de nombres qui ont une diff K.

Sample Input #00: 
5 2 
1 5 3 4 2 
Sample Output #00: 
3 
Sample Input #01: 
10 1 
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Sample Output #01: 
0 

J'ai déjà une solution (et je ne l'ai pas été en mesure d'optimiser aussi bien que j'avais espéré). Actuellement, ma solution obtient un score de 12/15 lorsqu'elle est exécutée, et je me demande pourquoi je ne peux pas obtenir 15/15 (ma solution à un autre problème n'était pas aussi efficace, mais j'ai obtenu tous les points). Apparemment, le code est exécuté en utilisant "Mono 2.10.1, C# 4".

Alors, peut-on imaginer une meilleure façon d'optimiser cela? Le profileur VS dit d'éviter d'appeler String.Split et Int32.Parse. Les appels à Int32.Parse ne peuvent pas être évités, même si je suppose que je pourrais optimiser tokenizing le tableau.

Ma solution actuelle:

using System; 
using System.Collections.Generic; 
using System.Text; 
using System.Linq; 

namespace KDifference 
{ 
    class Solution 
    { 
     static void Main(string[] args) 
     { 
     char[] space = { ' ' }; 

     string[] NK = Console.ReadLine().Split(space); 
     int N = Int32.Parse(NK[0]), K = Int32.Parse(NK[1]); 

     int[] nums = Console.ReadLine().Split(space, N).Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray(); 

     int KHits = 0; 

     for (int i = nums.Length - 1, j, k; i >= 1; i--) 
     { 
      for (j = 0; j < i; j++) 
      { 
       k = nums[i] - nums[j]; 

       if (k == K) 
       { 
        KHits++; 
       } 
       else if (k < K) 
       { 
        break; 
       } 
      } 
     } 

     Console.Write(KHits); 
     } 
    } 
} 

Answer 1

Votre algorithme est toujours O (n^2), même avec le tri et le départ anticipé. Et même si vous avez éliminé le bit O (n^2), le tri est toujours O (n lg n). Vous pouvez utiliser un algorithme O (n) pour résoudre ce problème. est ici une façon de le faire:

Supposons que le jeu que vous avez est S1 = { 1, 7, 4, 6, 3 } et la différence est 2.

Construct l'ensemble S2 = { 1 + 2, 7 + 2, 4 + 2, 6 + 2, 3 + 2 } = { 3, 9, 6, 8, 5 }.

La réponse que vous recherchez est la cardinalité de l'intersection de S1 et S2. L'intersection est {6, 3}, qui comporte deux éléments, donc la réponse est 2.

Vous pouvez mettre en œuvre cette solution dans une seule ligne de code, à condition que vous avez séquence d'entiers sequence et entier difference:

int result = sequence.Intersect(from item in sequence select item + difference).Count(); 

La méthode Intersection créera une table de hachage efficace pour O (n) afin de déterminer l'intersection.

Answer 2

Essayez ceci (note, non testé):

1. Trier le tableau
2. Démarrer deux indices à 0
3. Si la différence entre les chiffres à ceux deux positions est égale à K, augmente le nombre et augmente l'un des deux index (si les nombres ne sont pas dupliqués, augmentez les deux)
4. Si la différence est plus grande que K, hausse de l'indice # 1
5. Si la différence est inférieure à K, l'indice augmente # 2, si cela placerait en dehors du tableau, vous avez terminé
6. Sinon, revenir à 3 et continuer

Essentiellement, essayez de garder les deux index séparés par différence de valeur K.

Vous devriez écrire une série de tests unitaires pour votre algorithme, et essayer de trouver des cas limites.

Answer 3

Cela vous permettrait de le faire en un seul passage. Utiliser des ensembles de hachage est bénéfique s'il y a beaucoup de valeurs à analyser/vérifier. Vous pouvez également utiliser un bloom filter en combinaison avec des ensembles de hachage pour réduire les recherches.

1. Initialiser. Soit A et B être deux ensembles de hachage vides. Soit c être zéro.
2. Boucle d'analyse. Analyser la valeur suivante v. S'il n'y a plus de valeurs, l'algorithme est terminé et le résultat est c.
3. Vérification arrière. Si v existe dans A puis incrémenter c et revenir au 2.
4. match de bas. Si v - K> 0 alors:
   • insert v - K dans A
   • si v - K existe dans B puis incrémenter c (et éventuellement supprimer v - K de B).
5. Correspondance élevée. Si v + K < 1E9 alors:
   • insert v + K en A
   • si v + K existe dans B puis incrémenter c (et éventuellement supprimer v + K de B).
6. Rappelez-vous. Insérer v dans B.
7. Revenir à la 2.

Answer 4

En fait, c'est trivialement à résoudre avec un hashmap:

D'abord mis chaque numéro dans un hashmap: dict((x, x) for x in numbers) dans le code pseudo "de pythony";)

Maintenant, vous n'avez qu'à parcourir tous les nombres de la table de hachage et vérifier si le nombre + K est dans le hashmap. Si oui, augmenter le nombre par un.

L'amélioration évidente de la solution naïve est de vérifier UNIQUEMENT la borne supérieure (ou inférieure), sinon vous obtenez le double résultat et vous devez ensuite diviser par 2 - inutile. C'est O (N) pour créer la hashmap en lisant les valeurs dans et O (N) en itérant, c'est-à-dire O (N) et environ 8loc en python (et c'est correct, je viens de le résoudre;))

Answer 5

Après la réponse de Eric, coller la mise en œuvre de la méthode Interscet ci-dessous, il est O (n):

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) 
{ 
    Set<TSource> set = new Set<TSource>(comparer); 
    foreach (TSource current in second) 
    { 
     set.Add(current); 
    } 
    foreach (TSource current2 in first) 
    { 
     if (set.Remove(current2)) 
     { 
      yield return current2; 
     } 
    } 
    yield break; 
} 

Answer 6

// solution php pour cette différence k

function getEqualSumSubstring($l,$s) { 
$s = str_replace(' ','',$s); 
$l = str_replace(' ','',$l); 

for($i=0;$i<strlen($s);$i++) 
{ 
    $array1[] = $s[$i]; 
} 
for($i=0;$i<strlen($s);$i++) 
{ 
    $array2[] = $s[$i] + $l[1]; 
} 
return count(array_intersect($array1,$array2)); 

} 

echo getEqualSumSubstring("5 2","1 3 5 4 2");