5
Viene fornito un array di n numeri, dove n è un numero pari. Il numero massimo e minimo di questi n numeri deve essere determinato. Devo conoscere i paragoni necessari?Massimi e minimi di un array
A
risposta
3
Può essere eseguito nel tempo O (n).
È possibile controllare questo link per riferimento
+0
Stai scherzando? Usando l'approccio naive può essere fatto in O (N) –
+0
@IvayloStrandjev: - Per favore correggimi se ho torto ma l'ho considerato un array 2D. Quindi è possibile nell'array 2D anche i.e, O (n) time? –
+0
'Viene fornito un array di n numeri, dove n è un numero pari. Il numero massimo e minimo di questi n numeri deve essere determinato. Non vedo alcuna menzione del 2D qui. OP chiede un modo per trovare il numero minimo e massimo di n numeri usando il numero minimo di confronti –
4
Esso può essere fatto utilizzando 3*n/2-2 confronti.
Per n == 2, è sufficiente confrontare i due numeri. Supponiamo ora di avere il minimo e il massimo per i primi numeri n-2. Confronta i restanti due numeri, quindi confronta il più grande con il massimo precedente e il più piccolo con il minimo precedente.
1
Per un array non ordinato può essere eseguito in circa 1.5n confronti. Puoi farlo confrontando coppie di elementi di un array e memorizzando min e locale max. Hai effettuato confronti n/2 per trovare (locali) massimo e n/2 per trovare il min. Quindi, in totale n in questa fase.
Ora si passa sopra la popolazione massima e minima e si trova il numero massimo e minimo globale. Ciò richiederebbe anche confronti n/2. Quindi n + n/2 = 1.5n.
Se l'array è ordinato si può trovare senza paragoni, dal momento che il numero più basso è in posizione 0 e il più alto sulla posizione N - 1.
Problemi correlati
- 1. Valori minimi e massimi Java nell'array
- 2. Ottenere valori minimi e massimi in PHP Array
- 3. Kendo UI Editor caratteri massimi e minimi
- 4. Ricerca di massimi/minimi locali in R
- 5. Come creare un Django FloatField con limiti massimi e minimi?
- 6. gnuplot: valori massimi e minimi in un intervallo
- 7. Trova i valori minimi e massimi di una funzione
- 8. Google maps, impostazione dei controlli di scorrimento minimi e massimi
- 9. jQPlot forza valori minimi e massimi statici sull'asse y
- 10. Selezione dei minimi locali e dei massimi da panda. Serie
- 11. Come estrarre e tracciare solo i picchi minimi e massimi di un array, -graph analysis- Con Matlab o excel
- 12. selezionare i valori massimi, minimi da due tabelle
- 13. XPath 1 e XPath 2 di ritorno risultati diversi quando si determina valori minimi e massimi
- 14. Ricerca di valori minimi, massimi e medi per gli elenchi annidati?
- 15. Ricerca dei massimi/picchi e dei minimi/valli degli istogrammi locali
- 16. Identificazione dei minimi e massimi importanti nelle serie temporali con Mathematica
- 17. Numeri minimi di minimizzazione dei quadrati minimi
- 18. Ottieni indici di n massimi in array java
- 19. Coefficienti di polinomi massimi
- 20. Testers massimi in TestFlight
- 21. Come trovare i minimi locali di un array multidimensionale uniforme in NumPy in modo efficiente?
- 22. 5 valori massimi in un dizionario Python
- 23. Valori massimi dell'accelerometro Android
- 24. valori massimi dal dizionario
- 25. Minimi quadrati ponderati - R
- 26. GridSplitter con vincoli minimi
- 27. correttezza e logica di algoritmo: passi minimi ad uno
- 28. Utilizzo di pesi minimi e disuguali in rpart
- 29. Ionic2 iOS minimi e le versioni di Android
- 30. Trova indici di più valori massimi in un vettore
Suggerimento: 3 * n/2-2 i confronti sono sufficienti . – Henrik
@ Henrik, per favore, puoi elaborare – user2170497