我在这里接受采访。还有一个面试问题我遇到了困难。计数no。 O（n）
“A玫瑰是玫瑰是玫瑰”写一个 算法，打印的 次出现的字符/字的数量。例如。 A - 3玫瑰 - 3是 - 2
还要确保在您打印 的结果，它们在 为了什么存在于原 句子。 所有这些都是为了n。
我确实得到了解决方案，按照原始句子中的顺序来计算句子中每个单词的出现次数。我用Dictionary<string,int>来做到这一点。但我不明白n的顺序是什么意思。这是我需要你们的解释。
有26个字符，所以你可以使用counting sort对它们进行排序，在你的计数排序中，你可以有一个索引来确定特定字符第一次访问以保存发生顺序。 [他们可以按照他们的数量和他们的发生排序，像基数排序]。
编辑：的话每个人都可以想想第一件事，是用哈希表和哈希插入的话，在这样算来，他们可以在O（n）的排序，因为所有的数字在1..n钢之内，你可以通过在O（n）中进行排序来对它们进行排序，也可以通过它们的出现来遍历字符串并改变相同值的位置。
需要计算字数。不是字符;） – 2011-03-06 06:19:00
@Sachin Shanbhag，字数小于字符串的长度，因此您可以使用计数排序来处理与字符相同的单词，并且如果您阅读的问题是...字符/字...可能是我错了但是这个解决方案适用于两者。 – 2011-03-06 06:20:48
Aaah ...问题中提到的字符意味着该句子可以包含一个或多个字符。在上面给出的例子中，它指的是字符“A”。但是，总而言之，问题是不要计数。的单词发生。 – 2011-03-06 06:22:41
n的顺序意味着您只能遍历一次字符串或n的较小倍数，其中n是字符串中的字符数。 因此，您存储字符串和其出现次数的解决方案是O（n），顺序为n，因为您仅循环一次完整字符串。 但是，它使用您创建的列表形式的额外空间。
是的。这很好，但是当我转到下一个字符串时，我需要首先检查该字符串是否已经存在于列表中。这是否也被认为是遍历并解释了秩序？ – 2011-03-06 06:20:18
是的，最简单的例子可能是O（n^2）。如果将列表长度乘以10，则会将操作次数（最差情况下）增加100次。 10倍于原始列表中要遍历的单词数量，10次搜索第二个列表中每个单词的数量。 – caveman 2011-03-06 06:32:08
@sachin是的，这也是额外的遍历，以克服你应该使用一些散列表，其中基于键的查找是直接的，即O（1）。一个语言中性的伪代码将是myStatistics ['rose'] ++，它将增加基于myStatistics键值的数组中的“玫瑰”计数。 – DhruvPathak 2011-03-06 06:39:24
Order N指大O计算复杂性分析，您可以在算法上获得良好的上限。这是一个我们早期在数据结构课程中涵盖的理论，所以我们可以折磨，我的意思是帮助学生获得设施，因为我们平衡地遍历，堆积如山的不同知识树，各不相同。在你的情况下，他们希望你的算法在计算时间内随着文本的增长而与文本的大小成比例增长。
这是对Big O notation的引用。基本上面试者意味着你必须用O（N）算法完成任务。
“Order n”指的是Big O notation。大O是数学家和计算机科学家描述函数行为的一种方式。当某人指定搜索字符串“按顺序n”时，这意味着函数执行所花费的时间随着该字符串的长度增加而线性增长。换句话说，如果你绘制了执行时间与输入的长度，你会看到一条直线。
说你的函数必须是n阶并不意味着你的函数必须等于O（n），那么一个大于O的函数小于O（n）也被认为是可以接受的。在你的问题案例中，这是不可能的（因为为了计算一个字母，你必须“触摸”那个字母，因此必须有一些依赖于输入大小的操作）。
一种可能的方法是线性遍历字符串。然后创建一个哈希和列表。这个想法是使用这个词作为散列键，并增加每个出现的值。如果该值在散列中不存在，则将该单词添加到列表的末尾。在遍历字符串之后，使用散列值作为计数顺序遍历列表。
该算法的顺序是O（n）。哈希查找和列表添加操作是O（1）（或非常接近它）。
Order N是对大O符号的引用。基本上，这意味着程序执行的操作数量应该随着数据的增加而线性缩放。如果你用一个1000字的字符串运行它，它将比在一个10字的字符串上运行多100倍。例如C中的strlen（）是线性的。 – caveman 2011-03-06 06:15:54
'List'或'Dictionary '？ –
2011-03-06 06:27:35
@Oscar - 编辑我的问题，谢谢。不知道我在想什么。列表只是一个数组。 :) – 2011-03-10 15:56:09