给定一个A[]包含n整数的未排序数组,如何创建一个算法来返回最常出现的元素？
我想你需要一种方法来计算元素出现的次数.我只能想出一个O(n 2)实现.我知道我需要首先使用排序算法,但如果我使用合并排序,那已经是O(n logn)的总运行时间了.我只对数据进行了排序,我不能在不进一步增加运行时的情况下查看元素.
ami*_*mit 10
对数组进行排序,然后,所有重复元素彼此相邻.
简单地迭代数组,同时保持a maxSeen和currSeen计数器,如果当前元素等于最后一个元素,则增加currSeen,否则 - 重置currSeen,并且maxSeen如果currSeen大于它则替换.
排序是O(nlogn),迭代一次是O(n),所以总计 O(nlogn + n) = O(nlogn)
这是家庭作业,所以按照这个指导方针来创建代码应该是你的任务.祝好运!
作为旁注,由于这至少与Element Distinctness Problem一样难,并且使用基于比较的算法不能比O(nlogn)更好.
旁注二,它可以O(n)使用哈希表在时间+空间中完成.
创建数据的直方图,这是一个哈希映射,其中一个键是一个元素,值是出现次数.然后,问题就是在此哈希表中找到最大值.
构建表是O(n)平均情况,找到最大值O(n).
然而O(n),这会使用额外的内存,并且O(n^2)在最坏情况下可能会恶化到时间.