elenco di link algoritmo per trovare le coppie aggiungendo fino a 10

Question

Si può suggerire un algoritmo che trovare tutte le coppie di nodi in un elenco di link che aggiungere fino a 10. Mi si avvicinò con il seguente.

  

Algoritmo:. Confronto ogni nodo, a partire dal secondo nodo, con ogni nodo partendo dal nodo testa fino al nodo precedente (precedente al nodo corrente confronto) e segnalare tutte queste coppie

Credo che questo algoritmo dovrebbe funzionare tuttavia la sua non certo il più efficiente con una complessità di O (n2).

Qualcuno può suggerire una soluzione che è più efficiente (forse richiede tempo lineare). nodi aggiuntivi o temporanei possono essere utilizzati da una soluzione così.

Answer 1

Se la loro gamma è limitata (dicono tra -100 e 100), è facile.

Crea un quant[-100..100] serie poi basta scorrere la tua lista collegata, eseguendo:

quant[value] = quant[value] + 1

Poi il ciclo seguente farà il trucco.

for i = -100 to 100:
    j = 10 - i
        for k = 1 to quant[i] * quant[j]
            output i, " ", j

Anche se la loro portata non è limitata, è possibile avere un metodo più efficiente di quello che avete proposto, di classificare i valori prima e poi solo mantenendo conta piuttosto che i singoli valori (uguale alla soluzione di cui sopra).

Ciò si ottiene mediante l'esecuzione di due puntatori, uno all'inizio della lista e uno alla fine. Quando i numeri presenti in tali puntatori aggiungere fino a 10, loro uscita e spostare il puntatore fine verso il basso e il puntatore start up.

Quando sono superiore a 10, spostare il puntatore fine verso il basso. Quando sono di meno, spostare il puntatore start up.

Questa si basa sulla natura ordinata. Meno di 10 significa che è necessario fare la somma più elevata (mossa avviare puntatore verso l'alto). Maggiore di 10 significa che è necessario fare la somma inferiore (puntatore fine verso il basso). Dato che sono sono duplicati nella lista (a causa dei conti), essendo pari a 10 significa che si sposta entrambi i puntatori.

Arresto quando i puntatori passano l'un l'altro.

C'è un altro po 'complicato e che quando i puntatori sono uguali e il valore di somme a 10 (questo può accadere solo quando il valore è 5, ovviamente).

Non uscita il numero di coppie in base al prodotto, piuttosto si basa sul prodotto di meno il valore 1. Questo perché un valore di 5 con conteggio di 1 in realtà non somma da 10 (dato che c'è una sola 5).

Quindi, per la lista:

2 3 1 3 5 7 10 -1 11

si ottiene:

Index    a  b  c  d  e  f  g  h
Value   -1  1  2  3  5  7 10 11
Count    1  1  1  2  1  1  1  1

• Si inizia puntatore p1 a a e p2 a h. Dal -1 + 11 = 10, è uscita quei due numeri (come sopra, lo fai N tempi in cui N è il prodotto dei conteggi). Quello è una copia di (-1,11). Poi si passa a p1 b e p2 a g.
• 1 + 10 > 10 quindi lasciare p1 a b, spostare verso il basso per p2 f.
• 1 + 7 < 10 così spostare p1 a c, lasciare p2 a f.
• 2 + 7 < 10 così spostare p1 a d, lasciare p2 a f.
• 3 + 7 = 10, uscita due copie (3,7) dal momento che il conteggio di d è 2, spostare p1 a e, p2 a e.
• 5 + 5 = 10 ma p1 = p2 modo che il prodotto è 0 Numero 0 o 0. Uscita niente, spostare p1 a f, p2 a d.
• Loop finisce dal p1 > p2.

quindi l'uscita generale era:

(-1,11)
( 3, 7)
( 3, 7)

che è corretto.

Ecco un po 'di codice di prova. Noterete che ho costretto 7 (il punto medio) per un valore specifico per il test. Ovviamente, non farebbe questo.

#include <stdio.h>

#define SZSRC 30
#define SZSORTED 20
#define SUM 14

int main (void) {
    int i, s, e, prod;
    int srcData[SZSRC];
    int sortedVal[SZSORTED];
    int sortedCnt[SZSORTED];

    // Make some random data.

    srand (time (0));
    for (i = 0; i < SZSRC; i++) {
        srcData[i] = rand() % SZSORTED;
        printf ("srcData[%2d] = %5d\n", i, srcData[i]);
    }

    // Convert to value/size array.

    for (i = 0; i < SZSORTED; i++) {
        sortedVal[i] = i;
        sortedCnt[i] = 0;
    }
    for (i = 0; i < SZSRC; i++)
        sortedCnt[srcData[i]]++;

    // Force 7+7 to specific count for testing.

    sortedCnt[7] = 2;
    for (i = 0; i < SZSORTED; i++)
        if (sortedCnt[i] != 0)
            printf ("Sorted [%3d], count = %3d\n", i, sortedCnt[i]);

    // Start and end pointers.

    s = 0;
    e = SZSORTED - 1;

    // Loop until they overlap.

    while (s <= e) {
        // Equal to desired value?

        if (sortedVal[s] + sortedVal[e] == SUM) {
            // Get product (note special case at midpoint).

            prod = (s == e)
                ? (sortedCnt[s] - 1) * (sortedCnt[e] - 1)
                : sortedCnt[s] * sortedCnt[e];

            // Output the right count.

            for (i = 0; i < prod; i++)
                printf ("(%3d,%3d)\n", sortedVal[s], sortedVal[e]);

            // Move both pointers and continue.

            s++;
            e--;
            continue;
        }

        // Less than desired, move start pointer.

        if (sortedVal[s] + sortedVal[e] < SUM) {
            s++;
            continue;
        }

        // Greater than desired, move end pointer.

        e--;
    }

    return 0;
}

Si noterà che il codice di cui sopra è tutto O (n), in quanto io non sono l'ordinamento in questa versione, solo in modo intelligente utilizzando i valori come indici.

Se il minimo è sotto lo zero (o molto alto al punto in cui sarebbe sprecare troppa memoria), si può semplicemente utilizzare un MINVAL per regolare gli indici (un altro O (n) la scansione per trovare il valore minimo e poi basta utilizzare i-minVal anziché i per indici di matrice).

E, anche se la gamma da bassa ad alta è troppo costoso sulla memoria, è possibile utilizzare una matrice sparsa. Dovrete risolvere la, O (n log n), e la ricerca per l'aggiornamento conta, anche O (n log n), ma che è ancora migliore rispetto alla O originale (n ² ). Il motivo per cui la ricerca binaria è O (n log n) è perché un singola di ricerca sarebbe O (log n), ma devi farlo per ogni valore.

Ed ecco l'output da una corsa di prova, che mostra le varie fasi di calcolo.

srcData[ 0] =    13
srcData[ 1] =    16
srcData[ 2] =     9
srcData[ 3] =    14
srcData[ 4] =     0
srcData[ 5] =     8
srcData[ 6] =     9
srcData[ 7] =     8
srcData[ 8] =     5
srcData[ 9] =     9
srcData[10] =    12
srcData[11] =    18
srcData[12] =     3
srcData[13] =    14
srcData[14] =     7
srcData[15] =    16
srcData[16] =    12
srcData[17] =     8
srcData[18] =    17
srcData[19] =    11
srcData[20] =    13
srcData[21] =     3
srcData[22] =    16
srcData[23] =     9
srcData[24] =    10
srcData[25] =     3
srcData[26] =    16
srcData[27] =     9
srcData[28] =    13
srcData[29] =     5
Sorted [  0], count =   1
Sorted [  3], count =   3
Sorted [  5], count =   2
Sorted [  7], count =   2
Sorted [  8], count =   3
Sorted [  9], count =   5
Sorted [ 10], count =   1
Sorted [ 11], count =   1
Sorted [ 12], count =   2
Sorted [ 13], count =   3
Sorted [ 14], count =   2
Sorted [ 16], count =   4
Sorted [ 17], count =   1
Sorted [ 18], count =   1
(  0, 14)
(  0, 14)
(  3, 11)
(  3, 11)
(  3, 11)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  5,  9)
(  7,  7)

Answer 2

Crea un set di hash (HashSet in Java) (potrebbe usare un array sparso, se i numeri sono ben delimitate-, vale a dire si sa che cadono in +/- 100)

Per ciascun nodo, controlla innanzitutto se il 10-n è nel set. Se è così, avete trovato un paio. In entrambi i casi, quindi aggiungere n al set e continuare.

Così, per esempio avete 1-6 - 3 - 4 - 9

1 - è 9 nel set? No

6-4? No.

3-7? No.

4-6? Sì! Stampa (6,4)

9-1? Sì! Stampa (9,1)

Answer 3

Questo è un mini problema sottoinsieme somma, che è NP completo.

Answer 4

Se si dovesse ordinare prima il set, si eliminerebbero le coppie di numeri che dovevano essere valutati.