如何在不重新排列数组元素的情况下计算数组中唯一数字的数量？

Question

我在对一个数组进行独特值的计数时遇到了困难，并且需要在不重新排列数组元素的情况下完成。

我该如何做到这一点？

- jarus

---

做作业没什么问题，只要不是直接抄答案就行了。（也就是说，拿答案为基础，再加以改进） - Arafangion

Answer 1

如果您有.NET 3.5，您可以通过LINQ轻松实现这一点：

int numberOfElements = myArray.Distinct().Count();

非 LINQ：

List<int> uniqueValues = new List<int>();
for(int i = 0; i < myArray.Length; ++i)
{
    if(!uniqueValues.Contains(myArray[i]))
        uniqueValues.Add(myArray[i]);
}
int numberOfElements = uniqueValues.Count;

- Quintin Robinson

---

非Linq的例子真的很糟糕，但如果这确实是一个作业问题，让Rich B想出一个更好的解决方案吧。😊（提示：你如何避免每个元素都要迭代整个数组？） - Arafangion

让Jarus提出更好的解决方案吧，为什么SO不允许编辑评论呢！？ - Arafangion

你可以删除注释并重写。那就是我做的。 - Devin Jeanpierre

您可以先删除再重新添加。编辑可能会影响对话的流畅性。 - andleer

@Arafangion 是的，通常需要删除并重新陈述。我知道你的意思，这就是为什么我会在与作业相关的问题中发布非优化解决方案，以便发帖者可以思考和练习。 - Quintin Robinson

Answer 2

这是一种更高效的非LINQ实现。

        var array = new int[] { 1, 2, 3, 3, 3, 4 };
        // .Net 3.0 - use Dictionary<int, bool> 
        // .Net 1.1 - use Hashtable 
        var set = new HashSet<int>();
        foreach (var item in array) {
            if (!set.Contains(item)) set.Add(item);
        }
        Console.WriteLine("There are {0} distinct values. ", set.Count);

- sambo99

---

为什么要使用<int，object>而不是<int，bool>？ - sharptooth

从性能角度来看，它们应该是完全相同的，我会清理一下，使用HashSet，使得这个演示代码看起来不那么丑。 - Sam Saffron

字典包含应该比列表包含在大数组上更快。 - Kevin Gale

你不需要测试 HashSet 是否包含某个值。如果已经包含，Add() 方法将不会执行任何操作。也许编译器知道如何优化，但否则你会获得轻微的性能提升。 - Chetan S

结果发现，对于已经存在的项目调用.Add比调用.Contains要慢，因此这完全取决于您的输入数组。 - Sam Saffron

Answer 3

O(n) 运行时间 max_value 内存使用

boolean[] data = new boolean[maxValue];
for (int n : list) {
   if (data[n]) counter++
   else data[n] = true;
}

- Jimmy Jazz

Answer 4

应该只计算不同的值，还是应该计算数组中的每个数字（例如，“数字5包含3次”）？

第二个要求可以通过计数排序算法的起始步骤来实现。
大致如下：

• 构建一个集合，其中索引/键是要计数的元素
• 将键连接到一个变量上，该变量保存键元素的出现次数
• 迭代数组
  • 增加键（array[index]）的值

此致

- user51478