求解 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
当数组极大时,效率不好,求如何改??!!
求解 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
当数组极大时,效率不好,求如何改??!!
|
mb4555Jul 11, 2017
1
先排序,然后取头尾两元素差绝对值
|
|
2
实际上就只找 A[]中距离最远的一对相等的数。
对于每一个值 X,用 dict ( hashmap )记录最左边的 X 位置。 然后在从左到右扫描 A[]的过程中,利用 dict 直接更新距离。 |
|
mb4555Jul 11, 2017
3
搞错了,好尴尬啊
|
|
junwuhuiJul 11, 2017 via Android
4
对值进行 hash,拉链,然后每个链遍历一次?
|
|
geelawJul 11, 2017
5
为什么你要发两次?
|
|
wingkouJul 11, 2017 via Android
8
用一个 map 记录第一次出现的位置,顺扫一遍过程中更新最大距离就好了吧
|