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

Question

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

我能想到一个解决方案，但它是 O(n^2)。建议更好的东西。

标签： c++implementation

Answer 1

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

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

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