python - Python中的相似性度量

我正在处理名为“相似性度量”的编码挑战。现在的问题是，我的代码在某些测试案例中可以正常工作，并且由于“时限超出”问题而失败。但是，我的代码没有错，输入10 ^ 4范围需要花费25秒以上的时间。

我需要知道我可以做些什么来使其更高效，我想不出比我的代码更好的解决方案。

问题是这样的：

  问题指出给定一个正整数数组，现在我们必须根据Q查询进行回答。

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

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

  输入格式

  第一行包含N，不。数组A中元素的数量
  第二行包含N个以空格分隔的整数，它们是数组A的元素
  第三行包含Q查询数量
  每个Q行包含L，R

  约束

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

  输出格式

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

  样本输入

样本输出

说明

[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

这是我的算法：


  接受输入并以其他方法测试范围
  输入将是L，R和数组
  对于L和R之间的差等于1，检查下一个元素是否相等，返回1，否则返回0
  如果差异大于1，则遍历数组
  进行嵌套循环以检查相同的元素，如果是，则将差异存储到maxVal变量中
  返回maxVal


我的代码：

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))

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

最佳答案

您可以尝试以下代码：

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）。

关于python - Python中的相似性度量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58155169/