使用单个循环在数组中查找重复项

Question

问题是有一个未排序的数组，最大值应该小于长度。我必须找到数组中的重复记录。条件是只使用一次循环。这是我目前所取得的进展。我想知道是否有其他方法可以实现这一点。

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

- Muneeb Zulfiqar

---

以前从未使用过C#，但Set ≠ Array，在大多数编程语言中，集合意味着HashSet，它对其每个元素强制执行唯一约束。 - photoionized

这是C#中的内容。Set ≠ Array。但我对这种方法有所担忧。我们使用临时空间并进行比较。如果需要的话，我们也可以使用列表。 - Muneeb Zulfiqar

你确定输入数组不包含 0 吗？因为那会破坏你的解决方案。考虑使用 bool[] Arr2。 - H H

@tia 是的，未排序的正整数数组。 - Muneeb Zulfiqar

那么你的前置条件确保了必定存在重复。考虑长度为2的数组，它只能是{1, 1}。 - tia

Answer 1

使用任何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
  }

- Dmitry Bychenko

---

这不是一种相同的方法吗？你觉得呢？ - Muneeb Zulfiqar

@Mohit Jain：不，这个解决方案适用于任意整数，比如说“int [] Arr = { 5559，-2225，-56，23，-56 }；”，因此我宁愿不使用位数组。 - Dmitry Bychenko

@Abhi：不，当哈希实现正确时，它的时间复杂度是O(1)；这就是为什么该算法是线性O(n)（在数组上循环）的原因。 - Dmitry Bychenko

你的意思是一个没有冲突保证的哈希表？这怎么可能呢？此外，即使不使用任何C#结构，也可以解决这个问题。即使使用.NET，也可以使用Dictionary来实现相同的效果。在计算机科学中，我认为Contains()不能被称为O(1)。哈希只是用于均匀分布。 - Sourav 'Abhi' Mitra

@Abhi：不，哈希不能保证没有冲突，但是当哈希实现正确时，会有很少的冲突，这就是为什么平均包含时间是O(1)。然而，一个知道实现方法的对手可能会计算出这样的数字，使得许多冲突足以将Count变成线性。字典是基于哈希的，因此在解决方案中HasSet<T>和Dictionary<K, V>是可以互换的。 - Dmitry Bychenko

Answer 2

由于您有这个条件：

问题是有一个未排序的数组，最大值应该小于长度。

同时假设只有正数，在您的示例中适用

可以使用O(n)时间和O(1)空间来完成，而不使用任何LINQ、字典、哈希等。

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

- Sourav 'Abhi' Mitra

Answer 3

这是元素唯一性问题。

这个问题在没有额外空间的情况下无法被严格线性地解决。

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

1. 使用 HashSet - 在迭代时填充，如果找到匹配项则中止 - 平均需要 O(n) 时间和 O(n) 空间。
2. 排序并迭代，在数组排序后，重复项将相邻且易于检测。这需要 O(nlogn) 的时间和非常少的额外空间。

- amit

---

条件是只循环一次。如何在单个循环中进行排序和比较？ - Muneeb Zulfiqar

@MuneebZulfiqar foreach (var a in Arr.OrderBy(s => s)) - aevitas

OrderBy 这个循环执行了多次，先生。 - Muneeb Zulfiqar

@MuneebZulfiqar 这个答案旨在向您展示，并非我们想要的一切都能做到。这个问题无法在单个循环中解决，而不需要额外的空间，这应该给你一个提示，说明你正在正确的轨道上。 - amit

@amit 我有同样的想法，只是需要一些专家意见 :) - Muneeb Zulfiqar

Answer 4

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

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

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

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

- aevitas

---

无法使用Linq，因为它会违反使用单个循环的条件。 - Muneeb Zulfiqar

@MuneebZulfiqar 你说得对，GroupBy 实际上需要循环三次才能进行排序。 :) - aevitas

Answer 5

只有当数组a[]中包含范围在[0，n-1]内的数字{如您的问题所述}且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)！

- Aseem Goyal

Answer 6

尝试使用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);

- HackerMan