我必须找到给定数组中所有数字的周期，就像有很多解决方案一样，但是数组的大小为10 ^ 5

Question

例如给定的数组：[1,2,1,3,1,2,1,5]应该返回-

1 -> 2
2 -> 4
3 -> 0
5 -> 0

我可以想到一个解决方案，但它的解决方案是O（n ^ 2）。提出更好的建议。

Answer 1

在一次线性扫描中，将数组转换为按值索引的数组的哈希表，其中包含找到该值的索引。以您的示例为例：

{
  1: [0, 2, 4, 6],
  2: [1, 5],
  3: [3],
  5: [7],
}

然后，对于散列图中的每个条目l，如果0，则输出len(l) <= 1，否则输出l[1] - l[0]。如果还必须检查周期是否一致，请检查所有l[i] - l[i-1] == l[1] - l[0]的i >= 2。