确定数组是否包含重复值的最快方法是什么？

Question

该数组只能有一个重复项或根本没有。

我需要该算法通过一些单元测试，并拥有无法通过不同测试的不同版本。

如果您能发现这两个解决方案的任何问题或知道任何更快的解决方案，我将不胜感激。

散列：

对于具有或不具有重复值的 UInt16.MaxValue 大小的数组，这会导致持续时间测试失败。

通过 - 空数组不包含重复
通过 - 没有重复的小数组
通过 - 有重复（重复）的小数组
通过 - 有重复（重复）的小数组
通过 - 无重复（重复）的大数组
失败 - 无重复的大数组重复（持续时间）
通过 - 带重复（重复）的大型数组
通过 - 带重复（重复）的大型数组
失败 - 带重复（持续时间）的大型数组
失败 - 组合

public bool ContainsRepeat(UInt16[] values, out UInt16 repeat)
        {
            //HASH SET//
            var set = new HashSet<UInt16>();
            repeat = 0;
            foreach (UInt16 value in values)
            {
                if (!set.Add(value))
                {
                    repeat = value;
                    return true;
                }
            }
            return false;
         }

对重复项进行排序，然后进行二分查找：

对于相同大小的 UInt16.MaxValue 数组，这会导致持续时间测试失败，但仅当没有重复时才会失败，而且在存在重复时也无法返回正确的重复值，即使它适用于较小的数组。

通过 - 空数组不包含重复
通过 - 没有重复的小数组
通过 - 有重复（重复）的小数组
通过 - 有重复（重复）的小数组
通过 - 无重复（重复）的大数组
失败 - 无重复的大数组重复（持续时间）
通过 - 带重复（重复）的大型数组
失败 - 带重复（重复）的大型数组
通过 - 带重复（持续时间）的大型数组
失败 - 组合

public bool ContainsRepeat(UInt16[] values, out UInt16 repeat)
        {
            int findRepeatingElement(UInt16[] arr, int low, int high)
            {
                if (low > high)
                    return -1;

                int mid = (low + high) / 2;

                if (arr[mid] != mid + 1)
                {
                    if (mid > 0 && arr[mid] == arr[mid - 1])
                        return mid;

                    return findRepeatingElement(arr, low, mid - 1);
                }

                return findRepeatingElement(arr, mid + 1, high);
            }

            repeat = 0;
            if (values.Length <= 1)
            {
                return false;
            }

            Array.Sort(values);

            int index = findRepeatingElement(values, 0, values.Length - 1);

            if (index != -1)
            {
                repeat = values[index];
                return true;
            }
            else
            {
                return false;
            }


        }

这是我的第一篇文章，因此也欢迎任何有关格式化未来问题的意见:)

Answer 1

创建 UInt16.MaxValue 元素的新布尔数组。使用此数组（而不是 HashSet）作为探针来标记已看到的值并检测后续的重复项。

public bool ContainsRepeat(UInt16[] values, out UInt16 repeat)
{
  var seen = new bool[UInt16.MaxValue]; // O(k) space/time; fixed with very small C
  foreach (UInt16 value in values)      // O(n) time; n <= k, with small C
  {
    if (seen[value]) {
      repeat = value;
      return true;
    }
    seen[value] = true;
  }
  repeat = 0;
  return false;
}

这具有 O(n+k) 时间和 O(k) 空间（k = 范围）的特性，固定。在这种情况下，k = 2^16 ~ 65k 并且 n <= k 作为第一个重复项终止搜索。

虽然两种探测实现都是 O(n)，但由于常数 (C) 较小，因此这应该比使用 HashSet 执行得更好。然而，例如，对于具有 UInt32 范围值（k = 范围，其中 k >> n）的数据集，这种方法并不可取，因为这样会付出恒定的初始化和内存成本。

此特征类似于基数排序以及与一般排序相关的空间与时间权衡。

也可以应用微观优化（确保在现实条件下进行基准测试）。清除现有数组与创建新数组；或者使用 int 和增量+检查与布尔检查+设置；或者通过使用 unsafe 来避免索引范围保护。

如果在“大”数组的情况下失败......祝“最快”好运。