Python中的相似性度量

Question

我正在研究这个名为Similarity Measure的编码挑战。现在的问题是我的代码在某些测试用例中工作正常，但由于时间限制超过问题而失败。但是，我的代码没有错，输入范围 25^4需要超过 4 秒。

我需要知道我能做些什么来提高效率，我想不出比我的代码更好的解决方案。

问题是这样的：

问题状态是给定一个正整数数组，现在我们必须根据 Q 查询来回答。

查询：给定两个索引 L，R，确定两个相同元素的索引的最大绝对差值位于 L 和 R 之间

如果在某个范围内，没有两个相同的输入，则返回 0

输入格式

第一行包含数组 A 中的 N 个元素。 第二行包含 N 个空格分隔的整数，这些整数是数组 A 的元素 第三行包含 Q 查询数 每条 Q 线包含 L、R

约束

1 <= N, Q <= 10^4
1 <= Ai <= 10^4
1 <= L, R <= N

输出格式

对于每个查询，在新行中打印 ans

示例输入

5
1 1 2 1 2
5
2 3
3 4
2 4
3 5
1 5

示例输出

0
0
2
2
3

解释

[2,3] - No two elements are same
[3,4] - No two elements are same
[2,4] - there are two 1's so ans = |4-2| = 2
[3,5] - there are two 2's so ans = |5-3| = 2
[1,5] - there are three 1's and two 2's so ans = max(|4-2|, |5-3|, |4-1|, |2-1|) = 3

这是我的算法：

1. 采用输入并以其他方法测试范围
2. 输入将为 L、R 和数组
3. 对于 L 和 R 等于 1 之间的差值，请检查下一个元素是否相等，返回 1，否则返回 0
4. 对于差异大于 1，循环遍历数组
5. 创建一个嵌套循环来检查相同的元素，如果是，则将差异存储到 maxVal 变量中
6. 返回最大价值

我的代码：

def ansArray(L, R, arr):
maxVal = 0
if abs(R - L) == 1:
if arr[L-1] == arr[R-1]: return 1
else: return 0
else:
for i in range(L-1, R):
for j in range(i+1, R):
if arr[i] == arr[j]:
if (j-i) > maxVal: maxVal = j-i
return maxVal
if __name__ == '__main__':
input()
arr = (input().split())
for i in range(int(input())):
L, R = input().split()
print(ansArray(int(L), int(R), arr))

请帮我解决这个问题。我真的很想学习一种不同的、更有效的方法来解决这个问题。需要通过所有测试用例。:)

Answer 1

您可以尝试以下代码：

import collections

def ansArray(L, R, arr):
dct = collections.defaultdict(list)
for index in range(L - 1, R):
dct[arr[index]].append(index)
return max(lst[-1] - lst[0] for lst in dct.values())

if __name__ == '__main__':
input()
arr = (input().split())
for i in range(int(input())):
L, R = input().split()
print(ansArray(int(L), int(R), arr))

解释：

dct是一个字典，它为每个看到的数字保留一个索引列表。列表已排序，因此lst[-1] - lst[0]将给出此数字的最大绝对差异。将max应用于所有这些差异，您会得到答案。代码复杂度为 O(R - L(。

Answer 2

这可以大致通过以下方式解决为 O(N(：

from collections import defaultdict
def ansArray(L, R, arr) :
# collect the positions and save them into the dictionary
positions = defaultdict(list)
for i,j in enumerate(arr[L:R+1]) :
positions[j].append(i)
# create the list of the max differences in index
max_diff = list()
for vals in positions.values() :
max_diff.append( max(vals) - min(vals) )
# now return the max element from the list we have just created
if len(max_diff) :
return max(max_diff)
else :
return 0