如果你想要有固定的空间来找到最常见的元素，你需要有一个元素的最大位数。如果没有，那么大的输入数组可以有更大的输入数字，这样代表数字的位数大于固定空间来存储结果。

If you want to have fixed space to find the most common element you need to have a maximum number of bits for an element. If you didn't, then large input arrays could have larger input numbers such that the bits to represent the number is bigger than your fixed space to store the result.

假设 k 是您支持的最大数量的长度。如果您尝试天真地创建一个数组 2 ^ k 桶来计算每个数字的出现次数（计数器排序），您可以接收一个由相同数字组成的数组，在这种情况下您的算法将最终需要 log（n）空间来存储总和。[*]

Suppose k is the length of the largest number you support. If you try to naively create an array of 2^k buckets to count occurrences of each number (counter sort) you could receive an array consisting of the same number, in which case your algorithm would end up needing log(n) space to store the sum.[*]

如果我们看在一个更简单的问题的版本 - 确定是否有更多的 1 或$ code> 0 输入，我想你需要一个堆栈来做这个（你存储多少 1 或 0 是领先的）即使我们将输入长度限制为 k = 1 位的大小也是不可能的，所以不可用空间。

If we look at a simpler version of the problem - determine whether or not there are more 1's or 0's in an input, I think you need a stack to do this (you store how much 1 or 0 is leading by), and so constant space just isn't possible, even if we limit the input length to k = 1 bit in size.

您的问题更为通用（ k> 1 ，但仍然修复），并且还需要非常数空间，因此不可能，因为问题是如果您假设计数器具有 O（1）空间复杂性，那么您可以采取以下措施：

Your problem is more general (k > 1, but still fixed), and would also need non-constant space, so it's not possible, as the question is worded.

计数器排序方法，虽然这样做，你已经放置输入数组的最大大小的上限（可能或可能不可接受）：根据 k ，输入元素的最大位数您的数组和 c 您的数组中最多可以拥有的最大位数 2 ^ k * 2 ^ c 元素（其中一个计数器会在另一个元素上溢出）。为了解决这个问题，您可以添加一个 O（1）时间步长来减少您的计数器，使最小值始终为 0 $ c $如果所有计数器都不是 0 ，则每个元素都被处理，从而使它们相对而不是绝对值。这需要 O（1） time，因为如果全部都是非零，你只需要减少 O（2 ^ k）= O（1） counter by 1 如果您对每个元素执行它。虽然算法现在可以处理一些任意大的输入，但任何具有子数组的输入数组，使得两个值 a 和 b 是这样的， count（a） - count（b）> 2 ^ c = max（counter）使用计数器策略会失败一些输入。事实上，依赖于 O（1）空间复杂度计数器方法的结果是以 2 ^ c + 1 $开头的所有数组c $ c>这个算法无法处理相同的元素。

[*] If you assume counters have O(1) space complexity, then you can take the counter sort approach, although by doing so you've placed an upper-bound on the maximum size of your input array (which may or may not be acceptable): In terms of k, the maximum number of bits for an input element of your array and in terms of c the maximum number of bits in your counter your array can have at most 2^k * 2^c elements (one of the counters would overflow otherwise on the next element). To address this, you could add a O(1) time step to decrement your counters so that the minimum value is always 0 after each element is processed if all counters are non-0, thereby making them relative instead of absolute. This takes O(1) time because if all are non-zero you only need to decrement O(2^k) = O(1) counters by 1 if you perform it on each element. While the algorithm can now process some arbitrarily large inputs, any input array that has a sub-array such that two values a and b are such that count(a) - count(b) > 2^c = max(counter) using a counter strategy will fail for some inputs. In fact a consequence of relying on a O(1) space complexity counter approach is that all arrays that start with 2^c + 1 identical elements cannot be handled by this algorithm.