在具有单个循环的数组中查找重复项

本文关键字：查找 数组 单个 循环 | 更新日期: 2023-09-27 17:57:32

问题是有一个未排序的数组，最大值应该小于长度。我必须在数组中找到重复的记录。条件是只使用一次循环。这就是我迄今为止所取得的成就。我想知道是否还有其他方法可以让我做到这一点。

int[] Arr = { 9, 5, 6, 3, 8, 2, 5, 1, 7, 4 };
int[] Arr2 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < Arr.Length; i++)
{
    if (Arr2[Arr[i]] == 0)
    {
        Arr2[Arr[i]] = Arr[i];
    }
    else
    {
        Console.WriteLine("duclicate found");
    }       
}

在具有单个循环的数组中查找重复项

使用任何Set实现，例如HashSet<T>，例如

HashSet<int> hs = new HashSet<int>();
int[] Arr = { 9, 5, 6, 3, 8, 2, 5, 1, 7, 4 };
foreach (item in Arr) 
  if (hs.Contains(item)) {
    Console.WriteLine("duplicate found");
    // break; // <- uncomment this if you want one message only
  }
  else 
    hs.Add(item);

编辑：由于hs.Add返回bool，因此可以放入更短、更高效的代码：

HashSet<int> hs = new HashSet<int>();
int[] Arr = { 9, 5, 6, 3, 8, 2, 5, 1, 7, 4 };
foreach (item in Arr) 
  if (!hs.Add(item)) {
    Console.WriteLine("duplicate found");
    // break; // <- uncomment this if you want one message only
  }

既然你有这个条件：

The question is there is and unsorted array and the maximum value should be smaller than the length.

同样假设只有positive数字，在您的示例中应用

这可以使用O(n)时间和O(1)空间来完成，而无需使用任何LINQ、Dictionary、Hashing等。

int[] arr = { 9, 5, 6, 3, 8, 2, 5, 1, 7, 4 };
for (int i = 0; i < arr.Length; i++)
{
     if (arr[Math.Abs(arr[i])] >= 0)
         arr[Math.Abs(arr[i])] = -arr[Math.Abs(arr[i])];
     else
         Console.WriteLine("Duplicate found " + Math.Abs(arr[i]).ToString() + "'n");
}

这就是元素差异性问题。

如果没有额外的空间，这个问题就不能严格地线性求解。

解决该问题的两种常见方法是：

  1. 使用HashSet-在迭代时填充它，如果发现匹配，则中止-平均时间为O（n），空间为O（n）
  2. 排序和迭代，数组排序后，重复项将彼此相邻，并且易于检测。这是O(nlogn)时间，几乎没有额外的空间

使用LINQ获取所有重复项的最快方法是：

var duplicates = Arr.GroupBy(s => s).SelectMany(d => d.Skip(1));

这将返回Arr中所有重复元素的IEnumerable，您可以使用以下检查来包含是否存在任何重复：

if (duplicates.Any())
{
    // We have a duplicate!
}

如果只有数组a[]包含范围[0,n-1]{as in your question}中的数字，并且n不是很大，则这将起作用，以避免整数范围溢出。

for(i=0;i<n;i++)
{
    if(a[a[i]%n]>=n)
         **duplicate is a[i]** !
    else   
    a[a[i]%n]+=n;
}

时间复杂度：O（N）
空间复杂度：O（1）！

使用LINQ 尝试此代码

    int[] listOfItems = new[] { 4, 2, 3, 1, 6, 4, 3 };
var duplicates = listOfItems
    .GroupBy(i => i)
    .Where(g => g.Count() > 1)
    .Select(g => g.Key);
foreach (var d in duplicates)
    Console.WriteLine("The duplicate is "+d);
相关文章：