Trovare il numero possibile di coppie uguali in un array

Aug 23 2020

Ho fatto questo test online la scorsa settimana. ecco un esempio:

dato questo array:

{1, 2, 4, 5, 1, 4, 6, 2, 1, 4}

a condizione che

indice (x) <indice (y)

trova il numero di coppie possibili (x, y).

dove x = y.

la risposta sarebbe:

conteggio = 7 - (0,4), (0,8), (4,8), (1,7), (2,5), (2,9), (5,9)

Modifica3: immagine aggiunta per chiarire che le coppie sono elementi dello stesso array. l'immagine ha le prime 3 paia.

la prima soluzione che mi è venuta che ovviamente era cattiva:

public static int solution(int[] A)
    {
        int count = 0;
        for (int i = 0; i < A.Length; i++)
        {
            for (int j = i + 1; j < A.Length; j++)
            {
                if (A[i] == A[j])
                    count++;
            }
        }
        return count;
    }

fondamentalmente, conta solo il numero di coppie possibili in ogni ciclo.

poi dopo un po 'di fatica sono riuscito a farlo:

public static int solution(int[] A)
        {     
            int count = 0;
            var dict = new Dictionary<int, int>();
            for (int i = 0; i < A.Length; i++)
            {
                if (!dict.Any(x => x.Key == A[i]))
                    dict.Add(A[i], 1);
                else
                    dict[A[i]]++;
            }

            foreach (var item in dict)
            {
                count += Factorial(item.Value) / 2 * Factorial(item.Value - 2);
            }

            return count;
        }

1- conta quante volte il numero è presente.

2- calcola le possibili coppie per ogni numero che è dato da questa formula:

dove n è il numero di ripetizioni er = 2 (coppia, 2 elementi)

Il fattoriale è solo una semplice implementazione della funzione.

Sento che c'è molto da migliorare su questo. cosa pensi?

Modifica: aggiunta la funzione fattoriale come richiesto:

public static int Factorial(int N)
        {
            return N == 0
                       ? 1
                       : Enumerable.Range(1, N).Aggregate((i, j) => i * j);
        }

Edit2: ho provato entrambi e ho ottenuto 20 secondi per il primo metodo e 500 ms per il secondo metodo migliorato.

il 100000 era il limite fissato dai dettagli del test.

ecco il codice per il test:

int[] testArray = new int[100000];
Random x = new Random();
for (int i = 0; i < testArray.Length; i++)
{                
   testArray[i] = x.Next(1, 10);
}
Stopwatch sw = new Stopwatch();
sw.Start();
solution(testArray);
sw.Stop();

Modifica4:

Beh, sembra che ho sbagliato!

il calcolo del fattoriale per numeri maggiori di 19 in intero non è possibile, fuori intervallo.

il peggio è che non ho nemmeno dovuto calcolarlo.

nella mia formula poiché r è una costante a cui potrei semplificarlo

n * (n -1) / 2

evitando così l'intera cosa.

Risposte

2 AlexLeo Aug 24 2020 at 07:06

In base al calcolo del numero di coppie, la tua affermazione è corretta. L'intero metodo di calcolo potrebbe essere semplificato da:

    public static List<KeyValuePair<int,int>> solution(int[] A)
    {

        //n(n-1)/2 number of pairs by a given set
        return  A.GroupBy(x => x).ToList().
            Select(y => new KeyValuePair<int, int>((y.Count() * (y.Count() - 1)) / 2, y.Key)).ToList();
    }