求解 Python 面试题：

这……不永远都是 0 么…

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

@capbone 是的，有考代么

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

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

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

```
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
```

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

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

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

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() )

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

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

@Valyrian 看错题了。。

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()])

一个小优化

'''

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

'''

回复怎么不支持 markdown 了

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

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

```

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

```

悲剧，评论吞代码


[Imgur]( )

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

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

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

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

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

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

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

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

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

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

@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

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

@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

```

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

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