2017-10-21 17 views
3

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) 
+0

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

+0

@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

+1

@ 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

Répondre

3

Voici la mienne (pas O (n), mais pas O (n^2) soit je suppose):

>>> def find_dict_position(s): 
     from collections import defaultdict 
     counter = defaultdict(int) 
     result = [] 
     less_count = 0 
     for e in s[::-1]: 
      less_count = sum(counter[c] for c in counter if c<e) 
      result.append(less_count) 
      counter[e] += 1 
     return reversed(result) 

>>> list(find_dict_position('PRIME')) 
[3, 3, 1, 1, 0] 
+0

Eh bien, si la liste est une liste de caractères, alors c'est _is_ en fait O (n) ... plus précisément il est délimité par O (26 * n), et puisque 26 est un facteur constant, il peut être ignoré. –

1

Indépendamment du fait que si vous pouvez le faire dans une petite complexité ou non, vous pouvez utiliser une compréhension de liste et une expression du générateur comme suit pour accélérer votre code et plus Pythonic.

In [7]: [sum(j > t for t in lst[i+1:])for i, j in enumerate(lst)] 
Out[7]: [3, 3, 1, 1, 0] 

Notez également que vous ne pouvez pas le faire en O (n), car après tout ce que vous avez besoin de comparer vos éléments ensemble, ce qui est un algorithme de type de tri que, dans le meilleur des cas peut être fait en O (nlong (n)).

+2

Si je ne me trompe pas, vous avez donné un O (n^2) ... –

0

Donc, fondamentalement, ce problème est de trouver le nombre de petits éléments sur le côté droit de position actuelle dans un tableau. Remplacez d'abord le tableau de caractères par leurs valeurs ASCII respectives. Que vous pouvez utiliser BST équilibré pour résoudre le problème.

Here est l'explication détaillée du nombre de découverte des éléments plus petits sur le côté droit d'un tableau. Complexité O (nLogn).

Mais ici, en tant qu'éléments de tableau ne sont que des caractères, il peut être fait en complexité O (n) selon l'algorithme écrit dans la réponse mshsayem.