求解 Python 面试题：

V2EX = way to explore

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

现在注册

已注册用户请登录

这是一个创建于 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

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

9 条回复 • 2017-07-11 14:24:58 +08:00

mb4555

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

先排序，然后取头尾两元素差绝对值

GtDzx

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

实际上就只找 A[]中距离最远的一对相等的数。
对于每一个值 X，用 dict （ hashmap ）记录最左边的 X 位置。
然后在从左到右扫描 A[]的过程中，利用 dict 直接更新距离。

mb4555

2017-07-11 13:55:19 +08:00

搞错了，好尴尬啊

junwuhui

2017-07-11 14:11:45 +08:00 via Android

对值进行 hash，拉链，然后每个链遍历一次？

geelaw

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

为什么你要发两次？

sunhk25

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

@junwuhui 我也是这个想法,当重复率高的时候效率应该还可以

sunhk25

2017-07-11 14:17:31 +08:00

@geelaw 之前的节点选错了 ”配件”

wingkou

2017-07-11 14:21:57 +08:00 via Android

用一个 map 记录第一次出现的位置，顺扫一遍过程中更新最大距离就好了吧

wingkou

2017-07-11 14:24:58 +08:00 via Android

原来 @GtDzx 已经说过一样的了😳