例如，数组的答案:
1, 11, 3, 95, 23, 8, 1
将是 1，因为所有其他元素只出现一次，而 1 出现两次。
我在 stackoverflow 上看到的很多类似于这个问题的问题都要求找到绝对多数(答案在长度为 n 的数组中至少出现 n/2)，或者使用排序或 a 来回答问题哈希表。前者不是我要问的，后者要么太慢( O(n log n) 用于排序)要么使用太多内存( O(n) 用于哈希表)。
这样的算法存在吗？如果不是，是否有证据表明为什么不可能？包括一个来源会很好。
最佳答案
如果你想用固定的空间来找到最常见的元素，你需要有一个元素的最大位数。如果您不这样做，那么大型输入数组可能有更大的输入数字，这样表示数字的位就比您用来存储结果的固定空间大。
假设k是你支持的最大数的长度。如果您尝试天真地创建一个 2^k 桶数组来计算每个数字的出现次数(计数器排序)，您可能会收到一个由相同数字组成的数组，在这种情况下，您的算法最终需要log(n) 空间来存储总和。[*]
如果我们看一个更简单的问题 - 确定输入中是否有更多的 1 或 0，我认为你需要一个堆栈来做到这一点(你存储多少 1 或 0 领先)，所以恒定的空间是不可能的，即使我们将输入长度限制为k = 1 位大小。
你的问题更笼统(k > 1，但仍然是固定的)，并且还需要非常量空间，所以这是不可能的，因为问题的措辞。
[*] 如果您假设计数器具有 O(1) 空间复杂度，那么您可以采用计数器排序方法，尽管这样做您已经为最大大小设置了上限输入数组的最大位数(可能会或可能不会被接受):根据 k，数组输入元素的最大位数和 c数组中计数器的最大位数最多可以包含 2^k * 2^c 元素(否则其中一个计数器会在下一个元素上溢出)。为了解决这个问题，您可以添加一个 O(1) 时间步来递减您的计数器，这样如果所有计数器都不是-0，从而使它们成为相对的而不是绝对的。这需要 O(1) 时间，因为如果所有非零，您只需要将 O(2^k) = O(1) 计数器递减 1 如果你在每个元素上执行它。虽然该算法现在可以处理一些任意大的输入，但任何具有子数组的输入数组使得两个值 a 和 b 都满足 count(a ) - count(b) > 2^c = max(counter) 使用计数器策略对于某些输入会失败。事实上，依赖于 O(1) 空间复杂度计数器方法的结果是，所有以 2^c + 1 相同元素开头的数组都无法由该算法处理.
关于algorithm - 数组中最常见的元素/确定性地在 O(n) 时间和 O(1) 空间中找到相对多数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11781720/