python - Python 中的相似性度量

Question

我正在致力于这项名为相似度测量的编码挑战。现在的问题是我的代码对于某些测试用例工作正常，并且由于时间限制超出问题而失败。不过，我的代码并没有错，输入范围10^4需要超过25秒。

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

问题是这样的:

Problems states that given an array of positive integers, and now we have to answer based upon the Q queries.

Query: Given two indices L,R, determine the maximum absolute difference of index of two same elements lies between L and R

If in a range, there are no two same inputs then return 0

INPUT FORMAT

The first line contains N, no. of elements in the array A The Second line contains N space separated integers that are elements of the array A The third line contains Q the number of queries Each of the Q lines contains L, R

CONSTRAINTS

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

OUTPUT FORMAT

For each query, print the ans in a new line

Sample Input

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

Sample Output

0
0
2
2
3

Explanation

[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. To take the input and test the range in a different method
2. Input will be L, R and the Array
3. For difference between L and R equal to 1, check if the next element is equal, return 1 else return 0
4. For difference more than 1, loop through array
5. Make a nested loop to check for the same element, if yes, store the difference into maxVal variable
6. Return 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))

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

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