C# 如何在不重新排列数组元素的情况下计算数组中的唯一数字？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/613671/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I count the unique numbers in an array without rearranging the array elements?
提问by jarus
I am having trouble counting the unique values in an array, and I need to do so without rearranging the array elements.
我在计算数组中的唯一值时遇到问题，我需要在不重新排列数组元素的情况下这样做。
How can I accomplish this?
我怎样才能做到这一点？
回答by Quintin Robinson
If you have .NET 3.5 you can easily achieve this with LINQ via:
如果您有 .NET 3.5，您可以通过 LINQ 轻松实现这一点：
int numberOfElements = myArray.Distinct().Count();
Non LINQ:
非 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;
回答by Sam Saffron
This is a far more efficient non LINQ implementation.
这是一种效率更高的非 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);
回答by user51478
Should only the distinct values be counted or should each number in the array be counted (e.g. "number 5 is contained 3 times")?
应该只计算不同的值还是应该计算数组中的每个数字（例如“数字 5 包含 3 次”）？
The second requirement can be fulfilled with the starting steps of the counting sort algorithm.
It would be something like this:
第二个要求可以通过计数排序算法的起始步骤来满足。
它会是这样的：
- build a set where the index/key is the element to be counted
- a key is connected to a variable which holds the number of occurences of the key element
- iterate the array
- increment value of key(array[index])
- 构建一个集合，其中索引/键是要计数的元素
- 一个键连接到一个变量，该变量保存键元素的出现次数
- 迭代数组
- 键的增量值（数组[索引]）
Regards
问候
回答by user51478
O(n) running time max_value memory usage
O(n) 运行时间 max_value 内存使用
boolean[] data = new boolean[maxValue];
for (int n : list) {
if (data[n]) counter++
else data[n] = true;
}
