Как найти все символы в строке, внешний вид которых больше 2

Question

У меня вопрос по алгоритму:

Как найти все символы в строке, внешний вид которых больше определенного числа, скажем, 2, например, эффективно?

Привет.

Answer 1

Подсчет сортировки будет чрезвычайно эффективен для однобайтовых кодировок, граничный регистр - двухбайтовые кодировки. Для более широких кодировок это не так эффективно, но счетный массив можно заменить на хеш-таблицу.

РЕДАКТИРОВАТЬ: Кстати, это слишком общее решение, делать только подсчет фазы и вывод результатов на лету будет более чем достаточно.

Answer 2

s= #your string
h=Hash.new(0)

s.each_char {|c| h[c]+=1 }
h.select {|char,count| count>2}

Answer 3

Не удержался, чтобы попробовать это.

1. Хранить внутренний массив из 256 элементов для каждого (ASCII) символа.
2. Зациклите один раз над строкой ввода.
3. Увеличить счетчик для данного символа, используя порядковый номер символа в качестве прямого доступа к внутреннему массиву.

Реализация Delphi

Type
  TCharCounter = class(TObject)
  private
    FCounts: array[0..255] of byte;
  public
    constructor Create(const Value: string);
    function Count(const AChar: Char): Integer;
  end;

{ TCharCounter }

constructor TCharCounter.Create(const Value: string);
var
  I: Integer;
begin
  inherited Create;
  for I := 1 to Length(Value) do
    Inc(FCounts[Ord(Value[I])]);
end;

function TCharCounter.Count(const AChar: Char): Integer;
begin
  Result := FCounts[Ord(AChar)];
end;

Answer 4

var word = "......";
var chars = word.GroupBy(w => w).Where(g => g.Count > 2).Select(g => new { character = g.Key, count = g.Count });

Answer 5

более простой способ - использовать массив: вхождение [256], инициализировать их все с 0

и для каждого символа в строке вхождение [(int) char] ++.

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

Answer 6

Я бы отсортировал строку, затем просто прошел по ней и вел подсчет по каждой букве. Последнее - просто O (n), поэтому оно будет таким же эффективным, как и ваш.