Trova il secondo elemento più grande in un array?

Naviga le tue risposte
0

Il problema è risolverlo in n + logn-2 (base 2) no di confronti.

Il mio algoritmo richiede un po 'di spazio in più (O (n * n)). Come posso ridurre questo spazio extra senza aumentare la complessità. 

    comparisionarray=[][] (2D array )

    //a function to find the largest.
    findlargest(a,b)
       if(len(a)==1 and  len(b)==1)
          append b to array at ath index in comparisonarray.
          append b to array at bth index comparisionarray.
          return max(a,b)
       else
          return max(findlargest(1stHalfof(a),2ndHalfof(a)),findlargest(1stHalfof(b),2ndHalfof(b))

    input= input_array()
    largest=findlargest(1stHalfof(input),2ndHalfof(input))
    subarray=[array at index largest in comparisionarray]
    2ndlargest=findlargest(1stHalfof(subarray),2ndHalfof(subarray))
    print(2ndlargest)

Modifica: può essere eseguito con confronti minimi n + logn-2 . Questa è l'unica condizione. Questa risposta su math.stackexchange.com lo dimostra. È stato generalizzato per l'ennesimo elemento più grande

Sembra che ci sia una soluzione a questo link StackOverflow . Ma non sono sicuro dello spazio extra e della complessità temporale.

    
posta Arvind 09.05.2014 - 20:01
fonte

3 risposte

6

Sembra che tu stia cercando di fare una specie di dividi-e-conquisti che potresti trovare in un algoritmo di ordinamento. Ordinare e prendere il secondo valore dall'estremità grande funzionerebbe, ma è eccessivo per questo problema perché non hai davvero bisogno di avere il set di elementi ordinati quando hai finito.

La soluzione brute-force è O (n-1), esegue al massimo 2 * (n-1) confronti e occupa lo spazio equivalente a due dei membri del set: 

l1 := first_member_in_set  -- Largest value
l2 := first_member_in_set  -- Second-largest value

for each set member m after the first
    if m > l1
        l2 := l1
        l1 := m
    else if m > l2
        l2 := m
    end if
end for

Nota che affinché funzioni (e che ci sia un secondo membro per esteso), il set deve avere almeno due membri.

    
risposta data 09.05.2014 - 20:49
fonte
3

Penso che la definizione del problema potrebbe usare un po 'di lavoro .. Dato il presupposto che i dati non sono ordinati non vedo alcun motivo per cui non si possa risolvere questo in termini di confronti 2n al massimo, con una costante sostanziale memoria .. Mentre leggi l'array mantieni due variabili. Uno ha il più grande valore che hai trovato finora l'altro mantiene il secondo più grande. Ogni volta che trovi un nuovo massimo, spinga il vecchio alla seconda variabile.

    
risposta data 09.05.2014 - 20:45
fonte
0

Vuoi un collegamento di dimensioni 2. Questo si generalizza facilmente a code più grandi.

La solita implementazione è una forma array di un collegamento "heap". (Questo non è un tipo di allocatore di memoria di "heap".)

    
risposta data 10.05.2014 - 06:38
fonte

Leggi altre domande sui tag

Porting di un'implementazione dell'algoritmo con licenza GNU GPL v3 Quanto sono efficaci i certificati di firma del codice quando si tratta di comportamento o accettazione da parte dei clienti? [chiuso]