求解 Python 面试题：

[sunhk25]

求解 python 面试题：

def solution(A):
    N = len(A)
    result = 0
    for i in xrange(N):
        for j in xrange(N):
            if A[i] == A[j]:
                result = max(result, abs(i - j))
    return result

当数组极大时，效率不好，求如何改？？！！

[holajamc]

这……不永远都是 0 么…

[capbone]

计算相距最远的两个相等元素？
先用 argsort 返回排序序号，再分组求最大值，应该会高效不少吧？

[sunhk25]

@capbone 是的，有參考代碼么

[sunhk25]

@holajamc 0 並不重要，给的数组有一样的值就可以了，关键是算法

[capbone]

没... 我也只是随便一想给了个大概思路...

[braineo]

@capbone 记录出现过的 index 呢？不是 1 pass 么

[shuson]

```
def sol(A):
n = len(A)
for i in range(n):
j = n-1
while j > i:
if A[i] == A[j]:
return j - i
j -= 1
return 0
```

[geelaw]

用字典和合适的 hash 函数族可以做附加空间 O(n)，期望时间 O(n) 的。
用排序可以做附加空间 O(n)，时间 O(nlogn) 的。

[ZRS]

@shuson 这么改复杂度还是 N^2 这个级别的啊...

[holyghost]

hashmap 记录第一次出现该元素的 index
后面就是更新 max = (currentIndex - index) 了
空间 O(n) 时间 O(n)

[shuson]

https://gist.github.com/shuson/bd2185b72114f868bb59d6affefca4da

[tkpc]

V = {}
for i,x in enumerate(A):
if x in V: V[x][1] = i
else: V[x] = [i,i]
print max( (b-a) for a,b in V.itervalues() )

[Valyrian]

难道不是直接 return max(A) - min(A)

[csdreamdong]

0 0 我果然还是菜。。真心求问。这题想描述什么问题。

[Valyrian]

@Valyrian 看错题了。。

[yunkchen]

import collections

def solution(A):
l_count = collections.Counter(A)
repeats = [k for k, v in l_count.items() if v > 1]
ix_dict = collections.defaultdict(lambda: set())
for i in range(len(A)):
if A[i] in repeats:
ix_dict[A[i]].add(i)
return max([max(ix_value)-min(ix_value) for ix_value in ix_dict.values()])

[chroming]

一个小优化

'''

def solution(A):
N = len(A)
result = 0
for i in xrange(N):
for j in xrange(i, N):
if A[i] == A[j]:
result = max(result, abs(i - j))
return result

'''

[chroming]

回复怎么不支持 markdown 了

把 for j in xrange(N)改成 for j in xrange(i, N):

[gimp]

谁帮我看着这个时间复杂度多少，谢谢

[ty89]

```

def foo(a):
m = {}
max_delta = 0
for current_index in xrange(len(a)):
s = a[current_index]
if not m.has_key(s):
m[s] = {'first_index':current_index}
delta = 0
else:
delta = abs(m[s]['first_index'] - current_index)

max_delta = max(max_delta, delta)
return max_delta

```