Trovare una somma intera in un array di 1 000 000

Question

Dato un ampio elenco di numeri interi (più di 1 000 000 valori), scopri quanti modi ci sono di selezionarne due che sommano a 0 .... domanda

Quello che ho fatto è creare un positivo lista intero casuale:

Random pos = new Random(); 
int POSNO = pos.Next(1, 1000000); 
lstPOS.Items.Add(POSNO); 
lblPLus.Text = lstPOS.Items.Count.ToString(); 
POSCount++; 

e ha creato un elenco negativo:

Random neg = new Random(); 
int NEGNO = neg.Next(100000, 1000000); 
lstNEG.Items.Add("-" + NEGNO); 
lblNegative.Text = lstNEG.Items.Count.ToString(); 
NegCount++; 

Per fare la somma controllando che sto usando:

foreach (var item in lstPOS.Items) 
{ 
    int POSItem = Convert.ToInt32(item.ToString()); 
    foreach (var negItem in lstNEG.Items) 
    { 
     int NEGItem = Convert.ToInt32(negItem.ToString()); 
     int Total = POSItem - NEGItem; 
     if (Total == 0) 
     { 
      lstADD.Items.Add(POSItem + "-" + NEGItem + "=" + Total); 
      lblAddition.Text = lstADD.Items.Count.ToString(); 
     } 
    } 
} 

So che questo non è il percorso più veloce. Ho preso in considerazione l'utilizzo di un array. Hai qualche suggerimento?

Answer 1

Si è tentato di evitare di controllare due numeri vicini (1, 2 sono vicini, 3, 4 sono chiusi), ma non è stato possibile evitare il controllo come (-100000, 1), (-1, 100000). La complessità del tempo è O (n^2). Per evitare che sia necessario prima ordinarli, quindi cercare da due direzioni.

var random = new Random(); 
var input = Enumerable.Range(1, 100).Select(_ => random.Next(200) - 100).ToArray(); 

Array.Sort(input); // This causes most computation. Time Complexity is O(n*log(n)); 
var expectedSum = 0; 
var i = 0; 
var j = input.Length - 1; 
while (i < j) // This has liner time complexity O(n); 
{ 
    var result = input[i] + input[j]; 
    if(expectedSum == result) 
    { 
     var anchori = i; 
     while (i < input.Length && input[i] == input[anchori]) 
     { 
      i++; 
     } 
     var anchorj = j; 
     while (j >= 0 && input[j] == input[anchorj]) 
     { 
      j--; 
     } 
     // Exclude (self, self) combination 
     Func<int, int, int> combination = (n, k) => 
     { 
      var mink = k * 2 < n ? k : n - k; 
      return mink == 0 ? 1 
       : Enumerable.Range(0, mink).Aggregate(1, (x, y) => x * (n - y)) 
       /Enumerable.Range(1, mink).Aggregate((x, y) => x * y); 
     }; 
     var c = i < j ? (i - anchori) * (anchorj - j) : combination(i - anchori, 2); 
     for (int _ = 0; _ < c; _++) 
     { 
      // C# 6.0 String.Format 
      Console.WriteLine($"{input[anchori]}, {input[anchorj]}"); 
     } 
    } 
    else if(result < expectedSum) { 
     i++; 
    } 
    else if(result > expectedSum) { 
     j--; 
    } 
} 

Answer 2

Il modo più veloce senza cernita !.

Prima di tutto si sa che la somma di due numeri interi è 0 solo quando hanno il valore uguale assoluto ma uno è negativo e l'altro è positivo. Quindi non è necessario ordinare. ciò di cui hai bisogno è Interseca l'elenco positivo con l'elenco negativo (confrontando il valore assoluto). il risultato sono numeri che hanno finito con la somma 0.

Intersect ha una complessità di tempo di O(n+m) dove n è la dimensione del primo elenco e m è la dimensione del secondo.

private static void Main(string[] args) 
{ 
    Random random = new Random(); 

    int[] positive = Enumerable.Range(0, 1000000).Select(n => random.Next(1, 1000000)).ToArray(); 
    int[] negative = Enumerable.Range(0, 1000000).Select(n => random.Next(-1000000, -1)).ToArray(); 

    var zeroSum = positive.Intersect(negative, new AbsoluteEqual()); 

    foreach (var i in zeroSum) 
    { 
     Console.WriteLine("{0} - {1} = 0", i, i); 
    } 
} 

È inoltre necessario utilizzare questo IEqualityComparer.

public class AbsoluteEqual : IEqualityComparer<int> 
{ 
    public bool Equals(int x, int y) 
    { 
     return (x < 0 ? -x : x) == (y < 0 ? -y : y); 
    } 

    public int GetHashCode(int obj) 
    { 
     return obj < 0 ? (-obj).GetHashCode() : obj.GetHashCode(); 
    } 
} 

Answer 3

Vediamo; la matrice è qualcosa di simile:

int[] data = new int[] { 
    6, -2, 3, 2, 0, 0, 5, 7, 0, -2 
    }; 

è possibile aggiungere fino a zero in due modi diversi:

1. a + (-a) // positiva + negativa
2. 0 + 0 // ogni due zeri

nell'esempio sopra ci sei cinque coppie:

-2 + 2 (two pairs): [1] + [3] and [3] + [9] 
    0 + 0 (three pairs): [4] + [5], [4] + [8] and [5] + [8] 

Quindi è necessario tenere traccia di coppie e zeri positivi/negativi. L'implementazione

Dictionary<int, int> positives = new Dictionary<int, int>(); 
Dictionary<int, int> negatives = new Dictionary<int, int>(); 
int zeros = 0; 

foreach(var item in data) { 
    int v; 

    if (item < 0) 
    if (negatives.TryGetValue(item, out v))  
     negatives[item] = negatives[item] + 1; 
    else 
     negatives[item] = 1; 
    else if (item > 0) 
    if (positives.TryGetValue(item, out v))  
     positives[item] = positives[item] + 1; 
    else 
     positives[item] = 1; 
    else 
    zeros += 1; 
} 

// zeros: binomal coefficent: (2, zeros) 
int result = zeros * (zeros - 1)/2; 

// positive/negative pairs 
foreach (var p in positives) { 
    int n; 

    if (negatives.TryGetValue(-p.Key, out n)) 
    result += n * p.Value; 
} 

// Test (5) 
Console.Write(result); 

nota, che non c'è alcun ordinamento e dizionari (cioè tabelle hash) vengono utilizzati per i positivi e negativi in ​​modo che il tempo di esecuzione sarà lineare, O(n); il lato oscuro dell'implementazione è che sono necessarie due strutture aggiuntive (vale a dire memoria aggiuntiva).Nel tuo caso (solo milioni interi - Megabyte) hai quella memoria.

Edit: terser, ma la soluzione meno leggibile Linq:

var dict = data 
    .GroupBy(item => item) 
    .ToDictionary(chunk => chunk.Key, chunk => chunk.Count()); 

    int result = dict.ContainsKey(0) ? dict[0] * (dict[0] - 1)/2 : 0; 

    result += dict 
    .Sum(pair => pair.Key > 0 && dict.ContainsKey(-pair.Key) ? pair.Value * dict[-pair.Key] : 0); 

Answer 4

Ecco un'altra soluzione che utilizza (eh) LINQ. Spero che il codice è auto esplicativo

Prima alcuni dati

var random = new Random(); 
var data = new int[1000000]; 
for (int i = 0; i < data.Length; i++) data[i] = random.Next(-100000, 100000); 

E ora la soluzione

var result = data 
    .Where(value => value != int.MinValue) 
    .GroupBy(value => Math.Abs(value), (key, values) => 
    { 
     if (key == 0) 
     { 
      var zeroCount = values.Count(); 
      return zeroCount * (zeroCount - 1)/2; 
     } 
     else 
     { 
      int positiveCount = 0, negativeCount = 0; 
      foreach (var value in values) 
       if (value > 0) positiveCount++; else negativeCount++; 
      return positiveCount * negativeCount; 
     } 
    }) 
    .Sum(); 

Teoricamente quanto sopra dovrebbe avere O (n) e O (M) complessità spaziale, dove M è il conteggio dei valori assoluti unici nell'elenco.