zlin3000 最近的时间轴更新 zlin3000 最近的时间轴更新 |
zlin3000V2EX 第 211071 号会员，加入于 2017-01-17 00:10:11 +08:00 |
zlin3000 最近回复了
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
```
```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
所以 时间成本并不会比原方案更大。
原方案时间复杂度 是 固定的 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 面试题： |
因为是求最远相同元素距离，感觉可以从最远距离直接下手，即最大的可能最远距离只有一种，即第一个元素和最后一个元素，下一层可能得到最远距离的是两种即第一个和倒数第二个，第二个和倒数第一个，然后以此类推。
Select Language