string - 计数没有。 O(n) 中的单词

Question

我正在接受采访。另一个面试问题我遇到了困难。

“A rose is a rose is a rose” Write an algorithm that prints the number of times a character/word occurs. E.g. A – 3 Rose – 3 Is – 2

Also ensure that when you are printing the results, they are in order of what was present in the original sentence. All this in order n.

我确实得到了解决方案，可以按照原始句子中出现的顺序计算句子中每个单词的出现次数。我用了Dictionary<string,int>去做吧。但是我不明白n的顺序是什么意思。这是我需要你们解释的事情。

Answer 1

有26个字符，所以可以用counting sort要对它们进行排序，在您的计数排序中，您可以有一个索引，该索引确定特定字符何时首次访问以保存出现顺序。 [它们可以根据它们的数量和它们的出现进行排序，如基数排序]。

编辑:按字数大家首先想到的就是用Hash表，在hash中插入字词，这样算出来，然后可以O(n)的时间排序，因为所有数字都在 1..n 钢内，您可以通过 O(n) 中的计数排序对它们进行排序，对于它们的出现，您可以遍历字符串并更改相同值的位置。