Optimización este C# algoritmo (K Diferencia)

Question

Este es el problema que estoy resolver (que es un problema de muestra, no es un problema real):

Dadas N números, [N < = 10^5] nos necesidad de contar los pares totales de números que tienen una diferencia de K. [K> 0 y K < 1E9]

formato de entrada: primera línea contiene N & K (enteros). La segunda línea contiene N números del conjunto. Todos los N números están seguros de ser distintos. Formato de salida: un entero diciendo que el no de pares de números que tienen un K. diff

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 

ya tengo una solución (y no he podido optimizar ella, así como que tenía esperado). Actualmente mi solución obtiene un puntaje de 12/15 cuando se ejecuta, y me pregunto por qué no puedo obtener 15/15 (mi solución a otro problema no fue tan eficiente, pero obtuve todos los puntos) Aparentemente, el código se ejecuta usando "Mono 2.10.1, C# 4".

¿Alguien puede pensar en una mejor manera de optimizar esto aún más? El perfilador VS dice que evite llamar a String.Split e Int32.Parse. Las llamadas a Int32.Parse no se pueden evitar, aunque creo que podría optimizar el tokenizar la matriz.

Mi solución actual:

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

Su algoritmo sigue siendo O (n^2), incluso con la clasificación y la salida anticipada. E incluso si elimina el bit O (n^2), el género sigue siendo O (n lg n). Puede usar un algoritmo O (n) para resolver este problema. Aquí hay una manera de hacerlo:

Supongamos que el conjunto que tiene es S1 = { 1, 7, 4, 6, 3 } y la diferencia es 2.

construir el conjunto S2 = { 1 + 2, 7 + 2, 4 + 2, 6 + 2, 3 + 2 } = { 3, 9, 6, 8, 5 }.

La respuesta que busca es la cardinalidad de la intersección de S1 y S2. La intersección es {6, 3}, que tiene dos elementos, por lo que la respuesta es 2.

Puede implementar esta solución en una sola línea de código, siempre y cuando tenga la secuencia de números enteros sequence y número entero difference:

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

El método Intersect construirá una tabla hash eficiente para usted que es O (n) para determinar la intersección.

Answer 2

Prueba esto (nota, no probado):

1. ordenar la matriz
2. Start dos índices a 0
3. Si la diferencia entre los números a los que dos posiciones equivalen a K, aumentan el recuento y aumentan uno de los dos índices (si los números no están duplicados, aumente ambos)
4. Si la diferencia es mayor que K, aumentar el índice # 1
5. Si diferencia es menor que K, aumentar el índice # 2, si eso lo coloca fuera de la matriz, ya está hecho
6. De lo contrario, volver a 3 y sigue

Básicamente, trata de mantener los dos índices separados por la diferencia de valor K.

Debe escribir una serie de pruebas unitarias para su algoritmo y tratar de encontrar casos extremos.

Answer 3

Esto le permitiría hacerlo en una sola pasada. Usar conjuntos de hash es beneficioso si hay muchos valores para analizar/verificar. También es posible que desee utilizar un bloom filter en combinación con conjuntos de hash para reducir las búsquedas.

1. Initialize. Deje que A y B sean dos conjuntos de hash vacíos. Deje c sea cero.
2. Parse loop. Parse el siguiente valor v. Si no hay más valores, el algoritmo está hecho y el resultado está en c.
3. Back check. Siv existe en A continuación de la subasta c y saltar de nuevo a 2.
4. Baja partido. Si v - K> 0 entonces:
   • inserto v - K en A
   • si v - K existe en B entonces Incremento c (y eliminar opcionalmente v - K de B).
5. Partido alto. Si v + K < 1E9 entonces:
   • inserto v + K en A
   • si v + K existe en B entonces incrementar c (y eliminar opcionalmente v + K de B).
6. Recuerde. Insertar v en B.
7. saltar de nuevo a 2.

Answer 4

En realidad eso es trivial para resolver con un HashMap:

Primero puso cada número en un HashMap: dict((x, x) for x in numbers) en "pythony" pseudo código;)

Ahora simplemente itera a través de cada número en el hashmap y verifica si el número + K está en el hashmap. Si es así, aumente la cuenta en uno.

La mejora obvia de la solución ingenua es SOLAMENTE comprobar el límite superior (o inferior), de lo contrario obtendrá los resultados dobles y tendrá que dividir por 2 después - inútil.

Esto es O (N) para crear el hashmap al leer los valores y O (N) al iterar, es decir, O (N) y aproximadamente 8loc en python (y es correcto, acabo de resolverlo; -))

Answer 5

Tras la respuesta de Eric, pegue la aplicación del método de Interscet abajo, es 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

// solución PHP para esta diferencia 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");