如何快速确定一个数组中是否存在重复的值？

Question

如何快速确定一个数组中是否存在重复的值？

c#arraysperformancetimeduplicates

3

这个数组最多只能有一个重复，或者不重复。

我需要这个算法通过一些单元测试，并且有不同版本来失败不同的测试。

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

哈希：

在 UInt16.MaxValue 大小的数组中，无论是否有重复值，这种方法都无法通过持续时间测试。

通过 - 空数组不包含重复项
通过 - 没有重复项的小数组
通过 - 重复项为 (Repeated) 的小型数组
通过 - 重复项为 (Repeat) 的小型数组
通过 - 没有重复项的大型数组 (Repeated)
失败 - 没有重复项的大型数组 (Duration)
通过 - 有重复项的大型数组 (Repeated)
通过 - 有重复项的大型数组 (Repeat)
失败 - 有重复项的大型数组 (Duration)
失败 - 综合

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的相同数组，该方法在没有重复项时无法通过持续性测试，同时在存在重复项时也无法返回正确的重复值，即使它可以用于较小的数组。

通过 - 空数组不包含重复项
通过 - 小型无重复项数组
通过 - 重复项的小型数组(Repeated)
通过 - 重复项的小型数组(Repeat)
通过 - 没有重复项的大型数组(Repeated)
不通过 - 没有重复项的大型数组(持续时间)
通过 - 重复项的大型数组(Repeated)
不通过 - 重复项的大型数组(Repeat)
通过 - 重复项的大型数组(持续时间)
不通过 - 组合

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;
            }


        }

这是我的第一篇文章，欢迎对我在这里提出问题的格式提供建议:)

- Andrei123

这些失败的测试中是否有任何异常被抛出？ - aybe

不行，但持续时间需要低于2毫秒。 - Andrei123

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user2864740 · Accepted Answer

创建一个具有UInt16.MaxValue个元素的新bool数组。使用该数组（而不是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)，例如，因为这会支付一个恒定的初始化和内存成本。

这个特征类似于基数排序和与一般排序相关的空间与时间的权衡。

还可以尝试进行微优化(确保在真实环境下进行基准测试)。清除现有数组 vs 创建新数组; 或使用int和增量+检查vs布尔检查 +设置;或通过使用不安全以避免索引范围守卫。

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