Python ~数组中的第一个覆盖前缀

Question

所以我最近在网上面试了一份工作。虽然我的专长是网络和网络安全。

我遇到了一个问题：

编写一个函数，该函数接受整数数组并返回该数组的第一个覆盖前缀。长度为N的数组A的“第一覆盖前缀”是最小的指数P，使得0 <= P <= N和A中的每个元素也出现在元素A到AP的列表中。例如，以下数组的第一个覆盖前缀: A = 5、3、19、7、3、3、5、7、3，因为从A到A3的元素包含数组A中的所有值。

虽然我不是程序员(在面试中选择了python3 )，

我想找人解释一下背后的逻辑。

我只是想学习，这已经困扰了我一天了。

Answer 1

您可以迭代所有元素，如果还没有看到(使用set有效地跟踪)，更新P：

A = [5, 3, 19, 7, 3, 5, 7, 3]

S = set()
P = 0 # you could set -1/None as default to account for empty lists?
for i, item in enumerate(A):  # iterate elements together with indices
    if item not in S:         # if we haven't seen this element yet
        P = i                 # update P as the current index
        S.add(item)           # add the element to the set

print(P)

输出：3