我必须找到给定数组中所有数字的周期，就像有很多解决方案但数组的大小是 10^5
I have to find the period of all numbers in an given array, like there are many solutions but size of the array is 10^5
例如。给定的数组：[1,2,1,3,1,2,1,5]
应该 return-1 -> 2
2 -> 4
3 -> 0
5 -> 0
有一个我能想到的解决方案，但它是O(n^2)。
建议更好的。
在一次线性扫描中将您的数组转换为按值索引的数组散列映射，其中包含找到该值的索引。对于您的示例，这将是：
{
1: [0, 2, 4, 6],
2: [1, 5],
3: [3],
5: [7],
}
然后对于 hashmap 中的每个条目 l 输出 0 如果 len(l) <= 1，否则输出 l[1] - l[0]。如果您还必须检查周期是否一致，请检查所有 i >= 2.
的 l[i] - l[i-1] == l[1] - l[0]
例如。给定的数组：[1,2,1,3,1,2,1,5]
应该 return-1 -> 2
2 -> 4
3 -> 0
5 -> 0
有一个我能想到的解决方案，但它是O(n^2)。 建议更好的。
在一次线性扫描中将您的数组转换为按值索引的数组散列映射，其中包含找到该值的索引。对于您的示例，这将是：
{
1: [0, 2, 4, 6],
2: [1, 5],
3: [3],
5: [7],
}
然后对于 hashmap 中的每个条目 l 输出 0 如果 len(l) <= 1，否则输出 l[1] - l[0]。如果您还必须检查周期是否一致，请检查所有 i >= 2.
l[i] - l[i-1] == l[1] - l[0]