En un torneo de tenis de N jugadores, cada jugador juega con todos los demás jugadores. La siguiente condición siempre se cumple: si el jugador P1 ha ganado el partido con P2 y el jugador P2 le ha ganado a P3, entonces el jugador P1 también ha derrotado a P3. Encuentra el ganador del torneo en el tiempo O(N) y en el espacio O(1). Encuentre el rango de jugadores en tiempo O (NlogN). Mi solución: la entrada es una matriz booleana donde el elemento matrix[i][j] indica si el jugador i gana al jugador j.
bool win[][]= { {0, 0, 1, 1, 1, 0, 1}, {1, 0, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 1, 0, 1}, {0, 0, 1, 1, 1, 0, 0} };Entonces el ganador podría ser encontrado como,
int winner = 0; for (int i = 1; i < PLAYER_COUNT; ++i) { if (win[i][winner]) winner = i; } return winner;Para obtener el rango de los jugadores, supongo que la clasificación topológica será la buena. Si el jugador 1 gana al jugador 2, entonces se agrega una ventaja como esta P1-> P2. Si el jugador 1 es el ganador aquí, tendría ventajas sobre todos los demás jugadores. Luego, la clasificación topológica con el ganador como vértice de origen dará el rango del jugador. ¿Es correcta mi solución? ¿Hay alguna otra solución eficiente? Cualquier ayuda sería genial, gracias de antemano.
La condición
Si el jugador P1 ha ganado el partido con P2 y el jugador P2 le ha ganado a P3
Está definiendo una ordenación total, es decir, si definimos P1 < P2 para " P2 derrotó a P1 ", tenemos una relación de ordenación transitiva < , que se puede usar exactamente como la relación regular less-than para ordenar o encontrar el máximo. Entonces, para la implementación, podemos definir el predicado bool lessThan(int p1, int p2) que simplemente buscará la relación p1 y p2 en la matriz en O(1) . Y luego use el predicado para la búsqueda "máxima", que es lineal ( O(N) ), o para ordenar (clasificación), que es O(N log N) .
Su enfoque para encontrar un ganador parece correcto. De hecho, suponga que el número ganador real es W Cuando en su ciclo tiene i==W , siempre tendrá win[i][winner]==1 , porque el jugador W ha ganado a todos los demás. Por lo tanto, configurará winner=W , y nunca más lo cambiará, porque nadie ha ganado W .
Su código también es O(N) , así que creo que resuelve el primer problema.
Para el segundo problema, sí, la ordenación topológica funcionaría, pero una implementación simple sería O(N^2) . Sin embargo, tenga en cuenta que su tabla de win en realidad proporciona un orden total estricto . Por lo tanto, puede simplemente aplicar cualquier algoritmo de clasificación estándar y comparar dos jugadores simplemente comprobando si uno ha ganado al otro. Es decir, solo usa
bool less(int playerA, int playerB) { return win[playerA][playerB]; } en std::sort .
Este concepto de orden total estricto también proporciona una prueba alternativa para su algoritmo para encontrar un ganador.
Aquí está el código completo para su ejemplo: http://ideone.com/99DIQk