在 O(n log n) 时间内计算数组中的出现次数
Count occurrences in an array in O(n log n) time
给定一个未排序的数组 A[]，其中包含 n 个整数，如何创建一种算法来 return 最常出现的元素？
我认为您需要一种方法来计算元素出现的次数。我只能找出一个 O(n2) 实现。我知道我需要先使用排序算法，但如果我使用归并排序，那已经是 O(n logn)) 的总运行时间了。我只对数据进行了排序，如果不进一步增加运行时间，我无法查看元素。
对数组进行排序，然后，所有重复的元素都相邻。
简单地迭代数组，同时持有 maxSeen 和 currSeen 计数器，如果当前元素等于最后一个元素，则增加 currSeen，否则 - 重置 currSeen，并且如果 currSeen 大于它，则替换 maxSeen。
排序是O(nlogn)，迭代一次是O(n)，所以总共O(nlogn + n) = O(nlogn)
这是家庭作业，因此遵循此指南创建代码应该是您的任务。祝你好运！
附带说明一下，因为使用基于比较的算法，这至少与 Element Distinctness Problem, and it cannot be done better than O(nlogn) 一样难。
旁注二，可以在 O(n) 时间 + space 内使用 hash-tables 完成。
创建数据的直方图，它是一个hash-map，其中key是一个元素，value是出现的次数。然后，问题会退化为在这个散列 table 中找到最大值。
构建 table 是 O(n) 平均情况，找到最大值是 O(n)。
然而，这会使用 O(n) 额外内存，并且在最坏的情况下可能会恶化到 O(n^2) 时间。
您猜对了，从对数组排序开始是个好主意。正如您所指出的，这会花费 O(n log n)。然后您可以扫描数组并逐个计算每个值的频率，并在进行时记住最频繁的值。这花费 O(n)。总成本为 O(n log n + n)，即 O(n log n).
要了解原因，请考虑 O(2n log n)。这肯定在 O(n log n) 中，因为 2n log n 在 n log n[= 的常数因子内25=]。并且 n log n + n 以 2n log n 为界，所以它也在 O(n log n) 中.
只需将字典中的每个数字存储为键，将值作为其初始计数，如果数字再次重复则增加该计数，否则将其输入字典。
遍历字典中每一个键值，值大的键值最大
解在n+n =2n ~> n
给定一个未排序的数组 A[]，其中包含 n 个整数，如何创建一种算法来 return 最常出现的元素？
我认为您需要一种方法来计算元素出现的次数。我只能找出一个 O(n2) 实现。我知道我需要先使用排序算法，但如果我使用归并排序，那已经是 O(n logn)) 的总运行时间了。我只对数据进行了排序，如果不进一步增加运行时间，我无法查看元素。
对数组进行排序，然后，所有重复的元素都相邻。
简单地迭代数组，同时持有 maxSeen 和 currSeen 计数器，如果当前元素等于最后一个元素，则增加 currSeen，否则 - 重置 currSeen，并且如果 currSeen 大于它，则替换 maxSeen。
排序是O(nlogn)，迭代一次是O(n)，所以总共O(nlogn + n) = O(nlogn)
这是家庭作业，因此遵循此指南创建代码应该是您的任务。祝你好运！
附带说明一下，因为使用基于比较的算法，这至少与 Element Distinctness Problem, and it cannot be done better than O(nlogn) 一样难。
旁注二，可以在 O(n) 时间 + space 内使用 hash-tables 完成。
创建数据的直方图，它是一个hash-map，其中key是一个元素，value是出现的次数。然后，问题会退化为在这个散列 table 中找到最大值。
构建 table 是 O(n) 平均情况，找到最大值是 O(n)。
然而，这会使用 O(n) 额外内存，并且在最坏的情况下可能会恶化到 O(n^2) 时间。
您猜对了，从对数组排序开始是个好主意。正如您所指出的，这会花费 O(n log n)。然后您可以扫描数组并逐个计算每个值的频率，并在进行时记住最频繁的值。这花费 O(n)。总成本为 O(n log n + n)，即 O(n log n).
要了解原因，请考虑 O(2n log n)。这肯定在 O(n log n) 中，因为 2n log n 在 n log n[= 的常数因子内25=]。并且 n log n + n 以 2n log n 为界，所以它也在 O(n log n) 中.
只需将字典中的每个数字存储为键，将值作为其初始计数，如果数字再次重复则增加该计数，否则将其输入字典。
遍历字典中每一个键值，值大的键值最大
解在n+n =2n ~> n