Как подсчитать уникальные числа в массиве, не переставляя элементы массива?

Question

У меня проблемы с подсчетом уникальных значений в массиве, и мне нужно сделать это без перестановки элементов массива.

Как мне это сделать?

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;

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

Answer 3

O (n) время работы max_value использование памяти

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

Answer 4

Должны ли учитываться только отдельные значения или должно учитываться каждое число в массиве (например, «число 5 содержится 3 раза»)?

Второе требование может быть выполнено с помощью начальных шагов алгоритма сортировки подсчета.
Это было бы что-то вроде этого:

• построить набор, где индекс / ключ элемент для подсчета
• ключ связан с переменной, которая содержит количество вхождений ключевого элемента
• итерация массива
  • приращение значения ключа (массив [индекс])

Привет