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

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

[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 时，虽然我判断了，但第二层循环等于又完全遍历了，是这个意思吧。