Have Geek Brain

How to find all characters in a string whose appearance is greater than 2

I have a question about the algorithm:

How to find all characters in a string whose appearance is greater than a certain number, like 2, for example, efficiently?

Sincerely.

+2


a source to share


6 answers


Sort sort will be extremely efficient for single-byte encodings, boundary case for double-byte encodings. For wider encodings this is not as efficient, but counting the array can be replaced with a hash table.



EDIT: By the way, this is too general a solution, doing just counting the phase and outputting the results on the fly will be more than enough.

+6


a source 


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

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


+2


a source 


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


a source


Couldn't resist it.

  • Store an internal 256-element array for each character (ASCII).
  • Loop over the input line.
  • Increment the counter for the given character using the ordinal value of the character as a direct access to the internal array.

Delphi implementation

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;
+1


a source


I would sort the string, then just loop through it and save the current table for each letter. The latter is just O (n), so it will be as efficient as your type.

0


a source


easier to use array: occurrence [256], initialize them all with 0

and for each char in the string, occurrences of [(int) char] ++.

And then you just scan the event to find the occurrence of symbols that match your criteria.

0


a source






More articles:


All Articles