Как найти самый редкий элемент в массиве?

Рейтинг: 1Ответов: 2Опубликовано: 28.01.2011

Есть большой массив

string[] = { "строка", "еще строка", "и еще одна строка", ... };

Очень многие строки совпадают. Как найти такую строку (необязательно все) в массиве, которая встречается реже всего?

Напрашивается решение: создать список структур

struct Stats
{
    string Element;
    int Count;
}

List<Stats> stats;

и, проходя по исходному массиву, заносить в список новую строку или наращивать счетчик, если строка уже есть в списке. А потом уже пройти по списку и выбрать тот, у которого счетчик наименьший.

Есть ощущение, что с linq можно сделать проще. Вопрос как?

c# linq
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Не удержался и, всё же, написал на LINQ :).

string[] arr = { /* ... */ };
var query = (from str in arr
    group str by str into uStr
    orderby uStr.Count()
    select uStr.Key).Take(1);
res = query.First();
▲ 3

Пока принимал душ придумал два решения (вернее, придумал-то много, выбрал два):

  1. Работает за линию (быстрее невозможно), памяти тратит много.
    Заводим словарь (Map\HashMap\HashTable), ключ — строка, значение — число. Пробегаемся по списку, подсчитываем для каждой строки количество вхождений. Выбираем строку с наименьшим.

  2. Работает чуть дольше, дополнительной памяти требуется O(1).
    Сортируем массив. Теперь все одинаковые элементы будут идти подряд. Пробегаемся по массиву, подсчитывая для каждого элемента количество его вхождений и храним минимум. Бонусная оптимизация: как только нашли уникальный элемент, его и возвращаем.

LINQ, боюсь, тут не нужен…