1

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

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

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

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

struct Stats
{
    string Element;
    int Count;
}

List<Stats> stats;

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

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

3
  • А Вам какая характеристика алгоритма важна: время работы, используемая память или простота кода?
    – kirelagin
    28 янв 2011 в 12:54
  • Главное - это простота кода. 28 янв 2011 в 13:02
  • Чёрт, я неправильно спросил :(. Я имел в виду не простоту кода, а его краткость. Поскольку через LINQ код, возможно, будет короче, но вряд ли проще…
    – kirelagin
    28 янв 2011 в 13:26

3 ответа 3

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, боюсь, тут не нужен…

1

Ну да, если без каких-то новомодных наворотов, то надо сделать мапу string -> count и фигачаить её. Можно попытаться на ходу выстраивать уже отсортированный список.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.