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

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

你想要最大的距离，所以我假设你搜索的数字更有可能在开头和结尾。这就是为什么我会同时从start和end遍历数组。

[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的起始值永远不会减小。Delphi代码：

  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)时间(平均)，需要源数组是非常量，并在最后销毁它。此外，它还限制了数组中可能的值(每个值的三位应保留给算法)。

问题中已经有一半的答案了。使用hashmap。如果一个数字命中两次，使用索引差异，更新到目前为止最好的结果，并从hashmap中删除这个数字以释放空间。要使其为O(1)空间，只需重用源数组即可。就地将数组转换为hashmap。

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

在将数组元素转换为hashmap单元时使用一个保留位。在开始时，它被清除。当一个值被重新排序到hashmap单元格时，此位将被设置。如果没有为覆盖的元素设置此位，则仅获取此元素以进行下一步处理。如果要覆盖的元素设置了此位，则此处存在冲突，请选择第一个未使用的元素(未设置此位)并覆盖它。

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

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

• 3保留了原始value
• ceil(log(n))位中的bits
• 32 - 3 - (ceil(log(n)))高位，用于元素在原始数组

中的位置

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

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