Commencer avec la ligne 1. Allez à droite jusqu'à ce que vous frappez la première 1. Puis allez vers le bas à la ligne 2, mais restent dans la même colonne et répétez le processus d'aller à droite jusqu'à ce que vous frappez une 1. Faire cela à plusieurs reprises. La ligne dans lequel vous dernier en escalier droit est votre réponse.
C'est un O(N+M) solution (pour une matrice NxM, ou O(N) pour un carré de la matrice NxN, telle que donnée dans la question).
À l'aide de votre exemple de:
0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1
L' .'ici représentent le chemin parcouru:
. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .
Cette solution fonctionne sur la non-carré matrices, tout en conservant un pire des cas O(N+M) l'efficacité d'une matrice NxM.
Pourquoi ce travail? La garantie que les numéros seront triés signifie que chaque ligne sera une série de 0 est suivi par une série de 1. De sorte que la grandeur d'une ligne est équivalent à la façon dont extrême droite, vous pouvez aller de l'avant de frapper un 1. Donc, si une ligne ne peut jamais vous aller plus loin en suivant simplement les de 0, alors il doit être plus que tout ce que nous avons traitées avant.
Le code Python:
li = [[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
ans, j = 0, 0
for i, row in enumerate(li):
while j < len(row) and row[j] == 0:
j += 1
ans = i
print "Row", ans+1, "".join(map(str, li[ans]))
Il y a aussi une solution plus simple, en raison de contraintes de toujours avoir un carré de la matrice NxN et les différentes lignes ensemble. Ensemble, ils signifient que la ligne avec la valeur la plus basse sera soit 0 0 ... 0 1 ou 0 0 ... 0 0. C'est parce qu'il y a N de N+1 nombres représentés dans la matrice, de sorte que le "manque" nombre est soit 0 (dans ce cas, la plus petite valeur représentée est de 1), ou c'est autre chose (la plus petite valeur est 0).
Avec cette connaissance, nous vérifions la deuxième colonne en partant de la droite pour un 0. Quand on trouve une, on regarde à sa droite, et qui contient un autre 0 nous avons notre réponse (il ne peut y avoir une ligne se terminant par un 0). Sinon, nous continuons à chercher de la colonne pour l'autre 0. Si nous ne trouvons pas autre 0, le premier que nous avons trouvé était la ligne que nous cherchez pour (il ne peut y avoir une ligne se terminant en 01 et puisqu'il n'y a aucune fin en 00, c'est la plus petite).
Le code Python:
li = [[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
for i, row in enumerate(li):
if row[-2] == 0:
ans = i
if row[-1] == 0:
break
print "Row", ans+1, "".join(map(str, li[ans]))
Cette solution répond à la question avec moins de difficulté en O(N), mais la généralisation de gérer les non-carré NxM matrices ou non distinct numéros fera son pire des cas, l'efficacité de O(N^2). Personnellement, je préfère la première solution.
