求解 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

```

[ty89]

悲剧，评论吞代码


[takeoffyoung]

http://imgur.com/F1f9twv

[takeoffyoung]

[Imgur]( )

[di94sh]

这样时间复杂度是不是 O(N)
[Imgur]( http://imgur.com/a/zTNYd)

[di94sh]

http://imgur.com/ppCYgLD

[Yvette]

没看错的话作用是求数组中相同值的最远距离吗，可以先 enumerator 之后根据 key 排序再找相同字段的最大长度，算法刚开始学不太懂怎么算时间复杂度……懂得麻烦帮忙看下

[zlin3000]

因为是求最远相同元素距离，感觉可以从最远距离直接下手，即最大的可能最远距离只有一种，即第一个元素和最后一个元素，下一层可能得到最远距离的是两种即第一个和倒数第二个，第二个和倒数第一个，然后以此类推。

[backto17]

@gimp o(n), 另外可以用 defaultdict, 可以少了自己去判断存不存在

[aaronzjw]

考虑下哪些元素重复，然后对重复的元素进行计算

[zlin3000]

这么一说，如果不考虑空间成本的情况下，时间应该是 O(n)，遍历数组，用字典记住每个元素出现的最初位置，然后一个 max value 记入当前最远距离。

[aaronzjw]

https://gist.github.com/jwz-ecust/f4d1d236d27777f0fd6167ae13ab3996

[QAPTEAWH]

动态规划
D(i,j) =
j - i, if item[i] = item[j], or
max{D(i+1, j), D(i, j-1)}

[cxyfreedom]

```
max([(len(l) - l[::-1].index(i) - 1) - l.index(i) for i in set(l)])
```

[sky101001]

第一反应是排序复杂度是 O(nlogn)，再比较相邻元素，复杂度是 O(n)，选出最大间隔 O(nlogn)。最终时间复杂度可以是 O(nlogn)。
不过总觉得有更快的方法，容我想想

[xiaket]

@Livid 从回复看，绝大多数人都希望回复支持 markdown, 至少求添加对代码块的支持....

[ArcticL]

@zlin3000 有一点是当 result 越小，甚至等于 0 时，时间成本比原方案更大
def solution(A):
arrayLength = len(A)
for result in range(arrayLength, -1, -1):
for i in range(arrayLength):
if i + result < arrayLength and A[i] == A[i + result]:
return result

[zlin3000]

@ArcticL
原方案时间复杂度 是 固定的 O （ n^2 ）
我的第一个方案，最差 case 是 O （ n^2 ），1 + 2 + 3 + 4 + 5 + ... + n-1 = (n*(n-1))/2
所以 时间成本并不会比原方案更大。

[ArcticL]

@zlin3000 有代码么？这些概念的东西不好理解。。。

[zlin3000]

@ArcticL 代码：
```python

def solution(A):
# 两个元素之间的可能最长距离为数组长度-1
max_dist = len(A) - 1

# 从最长距离开始逐渐往下递减
for dist in range(max_dist, 0, -1)：
# 因为是按距离长度查找， 固每次只要查看可能可以达成当前长度距离的数组
# 所以第一次只能是 第一个元素和最后一个元素；
# 第二次是第一个和倒数第二个， 第二个和最后一个元素； 第三次可以此类推
# 因此是 1 + 2+ 3 + ... + n-1
for i in range(len(A) - dist):
if A[i] == A[i+dist]:
return dist

# 如果循化结束没有答案，则表示没有匹配数组
return 0

```

[ArcticL]

@zlin3000 哦，我懂了，当 result=0 时，虽然我判断了，但第二层循环等于又完全遍历了，是这个意思吧。

[719465553]

新建一个数组放下标，快排之后一个 for 算下标差就好了