V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  zlin3000  ›  全部回复第 1 页 / 共 1 页
回复总数  4
2017-07-13 01:58:51 +08:00
回复了 sunhk25 创建的主题 配件 求解 Python 面试题:
@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

```
2017-07-12 18:07:18 +08:00
回复了 sunhk25 创建的主题 配件 求解 Python 面试题:
@ArcticL
原方案时间复杂度 是 固定的 O ( n^2 )
我的第一个方案,最差 case 是 O ( n^2 ),1 + 2 + 3 + 4 + 5 + ... + n-1 = (n*(n-1))/2
所以 时间成本并不会比原方案更大。
2017-07-11 16:40:51 +08:00
回复了 sunhk25 创建的主题 配件 求解 Python 面试题:
这么一说,如果不考虑空间成本的情况下,时间应该是 O(n),遍历数组,用字典记住每个元素出现的最初位置,然后一个 max value 记入当前最远距离。
2017-07-11 16:27:49 +08:00
回复了 sunhk25 创建的主题 配件 求解 Python 面试题:
因为是求最远相同元素距离,感觉可以从最远距离直接下手,即最大的可能最远距离只有一种,即第一个元素和最后一个元素,下一层可能得到最远距离的是两种即第一个和倒数第二个,第二个和倒数第一个,然后以此类推。
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2830 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 10ms · UTC 07:24 · PVG 15:24 · LAX 23:24 · JFK 02:24
Developed with CodeLauncher
♥ Do have faith in what you're doing.