Pour chaque index dans un tableau donné, je veux trouver la somme de la somme des distances entre cet index et d'autres indices qui ont la même valeur dans un tableau donné.

Donc pour [1,2,1,1,2,3], nous aurions [5,3,3,4,3,0] car

Pour l'indice 0) | 2-0 | + | 3-0 | = 5, pour l'indice 1) | 4-1 | = 3, ..., pour l'indice 3) | 3-0 | + | 3-2 | = 4, ... etc.

Voici ma tentative qui obtient TLE pour des tableaux de longueur proche de 10000.

Comment rendre ma solution plus efficace?

def getDistanceMetrics(arr):
    if len(arr) > 10**5 or len(arr) < 1:
        return -1
    for z in range(len(arr)):
        if arr[z] > 10**9 or arr[z] < 1:
            return -1

    # Write your code here
    hm = collections.defaultdict(set)

    for i,value in enumerate(arr):
        hm[value].add(i)

    ans = []

    for j,val in enumerate(arr):
        tmp = 0
        for element in hm[val]:
            tmp += (j-element) if (j-element) >= 0 else element - j       
        ans.append(tmp)

    return ans

J'apprécierais également de savoir pourquoi et où ma réponse est lente, car pour moi, cela ressemble à O (n), ce qui semble aussi bien que vous pourriez le faire ici.

0
Permian 1 juin 2020 à 16:00

3 réponses

Meilleure réponse

Au lieu d'itérer sur arr, vous pouvez itérer sur hm. disons que nous voulons calculer la distance où hm du numéro un est {a1, ..., an} et que nous voulons calculer la réponse pour a_k alors pour tout i

Cela se fera en temps linéaire sur tout.

# Write your code here
hm = collections.defaultdict(set)

for i,value in enumerate(arr):
    hm[value].add(i)

ans = [0] * len(arr)

for key in hm:
    p = 0
    for i in range(len(hm[key])):
        p += hm[key][i]
        ans[hm[key][i]] += hm[key][i] * (i+1) - p
    p = 0
    for i in range(len(hm[key]) - 1, -1, -1):
        p += hm[key][i]
        ans[hm[key][i]] += p - hm[key][i] * (len(hm[key]) - i)
return ans
1
Arman Babaei 1 juin 2020 à 13:23

Pour chaque élément du tableau, vous itérez une fois sur son hm.

Ainsi, dans le pire des cas, si nous avons beaucoup de nombres avec la même valeur (disons n), pour chaque élément, vous itérerez sur tout le tableau, qui est O (n ^ 2)

1
Arman Babaei 1 juin 2020 à 13:35
In [1]: a = [1,2,1,1,2,3]

In [2]: b = [sum(abs(n-m) for m, j in enumerate(a) if i==j) for n, i in enumerat
   ...: e(a)]

In [3]: b
Out[3]: [5, 3, 3, 4, 3, 0]
1
Osman Mamun 1 juin 2020 à 13:13