求解 Python 面试题：

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐配件

› PHILIPS 飞利浦六位分控电源转换器

› 三洋 eneloop 电池 & 充电器套装

Magic Mouse 用户必备

› 三洋 eneloop 8 色亮彩充电电池纪念版

› 罗技 M950 激光无线鼠标

Darkfield 技术，可以在任何平面上使用

› 罗技 G9X 激光游戏鼠标

› 罗技 M310 笔记本激光无线鼠标

这是一个创建于 2697 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

result

xrange

Python

41 条回复 • 2019-01-24 14:44:41 +08:00

holajamc

2017-07-11 13:49:53 +08:00

这……不永远都是 0 么…

capbone

2017-07-11 13:51:36 +08:00

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

sunhk25

2017-07-11 13:52:33 +08:00

@capbone 是的，有參考代碼么

sunhk25

2017-07-11 13:53:26 +08:00

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

capbone

2017-07-11 13:53:45 +08:00

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

braineo

2017-07-11 13:56:41 +08:00

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

shuson

2017-07-11 13:59:42 +08:00

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

2017-07-11 14:03:39 +08:00

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

ZRS

2017-07-11 14:04:24 +08:00

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

holyghost

2017-07-11 14:06:16 +08:00

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

shuson

2017-07-11 14:07:01 +08:00

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

tkpc

2017-07-11 14:08:51 +08:00

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

2017-07-11 14:14:15 +08:00

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

csdreamdong

2017-07-11 14:14:47 +08:00

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

Valyrian

2017-07-11 14:14:51 +08:00

@Valyrian 看错题了。。

yunkchen

2017-07-11 14:18:55 +08:00

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

2017-07-11 14:29:34 +08:00

一个小优化

'''

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

2017-07-11 14:30:27 +08:00

回复怎么不支持 markdown 了

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

gimp

2017-07-11 14:35:11 +08:00

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

ty89

2017-07-11 14:35:34 +08:00

```

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

2017-07-11 14:38:00 +08:00

悲剧，评论吞代码

![](

)

takeoffyoung

2017-07-11 15:03:41 +08:00

http://imgur.com/F1f9twv

takeoffyoung

2017-07-11 15:04:42 +08:00

[Imgur](

)

di94sh

2017-07-11 15:15:32 +08:00

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

di94sh

2017-07-11 15:16:08 +08:00

http://imgur.com/ppCYgLD

Yvette

2017-07-11 15:45:32 +08:00

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

zlin3000

2017-07-11 16:27:49 +08:00 via Android

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

backto17

2017-07-11 16:29:34 +08:00

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

aaronzjw

2017-07-11 16:31:49 +08:00 via Android

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

zlin3000

2017-07-11 16:40:51 +08:00 via Android

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

aaronzjw

2017-07-11 16:49:07 +08:00

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

QAPTEAWH

2017-07-11 17:56:04 +08:00

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

cxyfreedom

2017-07-11 18:27:48 +08:00

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

sky101001

2017-07-11 19:11:11 +08:00 via iPad

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

xiaket

2017-07-12 06:49:25 +08:00

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

ArcticL

2017-07-12 14:24:43 +08:00

@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

2017-07-12 18:07:18 +08:00

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

ArcticL

2017-07-12 20:19:48 +08:00

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

zlin3000

2017-07-13 01:58:51 +08:00

@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

2017-07-13 09:41:12 +08:00

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

719465553

2019-01-24 14:44:41 +08:00

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