找到给定数组中每个元素出现两次且距离最长的元素？

Question

给定一个 int 数组，每个 int 在数组中恰好出现两次 大批。找到并返回使得这对 int 具有最大值的 int 该数组中彼此之间的距离。

例如[2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4;
1: d = 3-2 = 1;
3: d = 6-4 = 2;
return 2

我的想法：

使用hashmap，key是a[i]，value是索引。扫描a[]，将每个数字放入哈希中。如果一个数字被击中两次，则用它的索引减去旧数字的索引，然后使用结果更新哈希中的元素值。

之后，扫描哈希并返回具有最大元素（距离）的键。 时间和空间上都是O(n)。

如何在 O(n) 时间和 O(1) 空间内做到这一点？

Answer 1

您希望拥有最大距离，因此我假设您搜索的数字更有可能位于开始和结束处。这就是为什么我会同时从开始和结束循环数组。

[2, 1, 1, 3, 2, 3]
Check if 2 == 3?
Store a map of numbers and position: [2 => 1, 3 => 6]
Check if 1 or 2 is in [2 => 1, 3 => 6] ?

我知道，这甚至不是伪代码，也不完整，只是为了给出这个想法。

Answer 2

将 iLeft 索引设置为第一个元素，将 iRight 索引设置为第二个元素。
增加 iRight 索引，直到找到左侧项目的副本或到达数组末尾。在第一种情况下 - 记住距离。

增加 iLeft。从新的 iRight 开始搜索。
iRight的起始值永远不会减少。
德尔福代码：

  iLeft := 0;
  iRight := 1;

  while iRight < Len do begin //Len = array size
    while (iRight < Len) and (A[iRight] <> A[iLeft]) do
      Inc(iRight); //iRight++
    if iRight < Len then begin
      BestNumber := A[iLeft];
      MaxDistance := iRight - iLeft;
    end;
    Inc(iLeft); //iLeft++
    iRight := iLeft + MaxDistance;
  end;

Answer 3

该算法的空间复杂度为 O(1)（有一些作弊），时间复杂度为 O(n)（平均），需要源数组是非常量的，并在最后销毁它。它还限制了数组中可能的值（每个值的三位应为算法保留）。

一半的答案已经在问题中了。使用哈希图。如果一个数字被击中两次，则使用索引差异，更新迄今为止最好的结果，并将该数字从哈希图中删除以释放空间。要使其成为 O(1) 空间，只需重用源数组即可。将数组就地转换为哈希图。

在将数组元素转换为哈希图单元之前，请记住它的值和位置。此后它可以被安全地覆盖。然后使用该值计算哈希图中的新位置并覆盖它。元素以这种方式打乱，直到找到空单元格。要继续，请选择尚未重新排序的任何元素。当一切都重新排序时，每个 int 对肯定会被命中两次，这里我们有一个空的哈希图和更新的最佳结果值。

将数组元素转换为哈希图单元时使用一位保留位。一开始它是清除的。当一个值被重新排序到哈希图单元时，该位被设置。如果对于被覆盖的元素没有设置该位，则仅将该元素作为下一个处理。如果为要覆盖的元素设置了该位，则此处存在冲突，请选择第一个未使用的元素（未设置该位）并覆盖它。

另外 2 个保留位用于链接冲突值。它们对链开始/结束/继续的位置进行编码。 （也许可以优化该算法，以便只需要 2 个保留位...）

哈希图单元应包含这 3 个保留位、原始值索引以及一些用于唯一标识该元素的信息。为了实现这一点，散列函数应该是可逆的，以便在给定值在表中的位置的情况下可以恢复部分值。在最简单的情况下，哈希函数只是 ceil(log(n)) 最低有效位。表中的值由 3 个字段组成：

• 3 保留位
• 32 - 3 - (ceil(log(n))) 原始值的高位
• ceil(log(n)) 位表示元素在原始数组中的位置

时间复杂度平均仅为 O(n)；最坏情况复杂度为 O(n^2)。

该算法的其他变体是将数组顺序转换为哈希图：在每一步 m 中，将数组的第一个元素 2^m 转换为哈希图。当 m 较低时，一些常量大小的数组可能会与哈希图交错以提高性能。当m很高时，应该有足够的int对，它们已经被处理，并且不再需要空间。

Answer 4

没有办法在 O(n) 时间和 O(1) 空间中做到这一点。