C'est un casse-tête intéressant que j'ai rencontré, selon lequel, étant donné un tableau, nous devons trouver l'indice Ninja.
Un indice Ninja est défini par ces règles:
Un indice K telle que tous les éléments avec des index plus petits ont des valeurs inférieures ou égales à un [k] et tous les éléments avec des index plus importants ont des valeurs supérieures ou égales à une [K].
Par exemple, envisagez:
Dans ce cas, Quel algorithme allons-nous suivre pour le trouver dans O (n). J'ai déjà une solution de force brute O (n ^ 2).
Edit: Il peut y avoir plus de 1 index Ninja, mais nous devons trouver le premier de préférence. Et au cas où il n'y a pas de NI, alors nous retournerons -1. a [0] = 4, A [1] = 2, A [2] = 2, A [3] = 3, A [4] = 1, A [5] = 4, A [5] = 4, A [ 6] = 7, A [7] = 8, A [8] = 6, A [9] = 9.
5 est un index Ninja, depuis un [r] <= a [5] pour r = [0, k] et a [5] <= a [R] r = [k, n].
4 Réponses :
Valeurs minimales précalcompute pour tous les suffixes de la matrice et des valeurs maximales pour tous les préfixes. Avec cette donnée, chaque élément peut être vérifié pour Ninja dans O (1).
Programmation dynamique pour la victoire da
@Claudiu, pourriez-vous y faire sortir sur l'exemple que j'ai fourni dans l'op
@steak.: Suffix Minima Array: Min = {1,1,1,1,1,4,6,6,6,9} , Préfixe Maxima Array: Max = {4 , 4,4,4,4,4,7,8,8,9} . Recherchez un index i tel que a [i] a [i-1]> max [i-1] . Pour i == 5 nous obtenons a [5] = 4, max [4] = 4, min [6] = 6 - et il satisfait des conditions
Et au cas où il n'est pas clair, calculez les matrices de suffixe et de préfixes dans O (n) (suffixe du dernier à la première El, il suffit de comparer l'élément actuel i Avec le suffixe min précédemment calculé ( i + 1 ); préfixe l'autre solution), puis la vérification finale prend O (n) , O (3n ) est dans o (n)
@amit merci. Cela clarifie.
une solution python qui prendra O (3N) Opérations
Eh bien c'est à peine compréhensible.
Vous devriez expliquer comment cela fonctionne. Une réponse du code unique est de l'utilité limitée. Et vous avez une erreur obsolète, si je ne me trompe pas. Mais c'est une bonne solution.
Une autre solution Python, à la suite de la même approche générale. Peut-être un peu plus court.
def ninja(lst):
maxs = lst[::]
mins = lst[::]
for i in range(1, len(lst)):
maxs[ i] = max(maxs[ i], maxs[ i-1])
mins[-1-i] = min(mins[-1-i], mins[-i ])
return [i for i in range(len(lst)) if maxs[i] <= lst[i] <= mins[i]]
Ce code Java à l'avance simple calcule l'indice le plus à gauche qui a la propriété "Tous les éléments à droite ne sont pas moins": presque même code calcule l'indice le plus à gauche "Toutes les éléments à gauche ne sont pas plus grand ": Si les résultats sont identiques, l'indice ninja le plus à gauche est trouvé.
Bon problème. Il peut être connecté à l'algorithme de tri bien connu: "Une seule phase Quickort vient d'être exécuté sur toute la table. Identifier les indices auraient pu être la valeur pivot"
Oui, j'ai aussi eu ça à l'esprit.