Supposons que j'ai une chaîne PRIME
dans une liste ['P','R','I','M','E']
. Si nous parcourons la liste, le premier élément 'P'
a 3 éléments de moins que celui qui est ['I','M','E']
et le deuxième élément 'R'
n'a que trois éléments de moins (notez que nous recherchons des éléments plus petits à l'avenir dans la liste afin de rechercher les éléments plus petits que 'R'
, 'P'
ne seraient pas considérés comme nous en avons fini avec) donc la liste de position serait [3,3,1,1,0]
dans l'exemple ci-dessus. Je pourrais le faire en o(n**2)
temps en utilisant une boucle imbriquée, mais est-il possible de le faire dans o(n)
? J'ai essayé quelque chose comme ça, mais il a échoué horriblement:Comment trouver la position d'un caractère dans une liste par rapport à d'autres caractères dans une liste en o (n) temps?
for _ in range(int(input())):
x=list(input())
y=sorted(x)
lis=[]
for _ in x:
res=abs(y.index(_)-x.index(_))
lis.append(res)
print(lis)
Cela semble être une tâche de programmation. Cependant, j'ai un indice pour vous, tout d'abord trier l'entrée, 'O (nlogn)', puis voir si vous pouvez déduire quelque chose des indices précédents et de nouveaux indices? – ZdaR
@downvoter Je pense que j'ai expliqué mon problème au mieux que je pouvais, aussi j'ai expliqué mon approche, mais il semble que c'est une tradition de voter la question ici quand quelqu'un ne sait pas à ce sujet – Demonking28
@ ZdaR Non, je J'essaie de trouver le rang d'un mot dans un dict (concept de permutation) et pour cela j'ai besoin de cela, bien que mon script fonctionne correctement c'est lent d'où le problème – Demonking28