在O（1）额外空间和O（n）时间内计算阵列中所有元素的频率

Question

问题描述：我在算法分配中发现了这个问题。它希望我在O（n）时间和O（1）空间中找到数组中所有元素的频率。

数组可以像Ar [] = {1,6,3,78,4,6,1}

思考了一下后我想出了这种方法：

1. 迭代数组并找到最大元素。（O（n）时间）
2. 创建size = max元素的新数组（O（1）空间）
3. 迭代原始数组并将频率存储在新数组的索引处（O（n）时间）。

我对步骤2有疑问。在步骤1中找到最大元素（比如m）后，我正在制作一个大小为m的新数组。事物数组占据O（1）空间吗？如果没有请解释

Answer 1

是的，您正确找到最大数量，然后创建该长度的哈希数组不是O（1）空间复杂度的解决方案，因为O（1）空间复杂度是指恒定的空间使用但是如果您声明数组的大小仅根据您的输入值，空间如何成为常量。常量空间或O（1）复杂性意味着一种不考虑输入值而不依赖于输入的方法。因此，您的这种方法对于解决方案来说是不正确的。希望，我已经说清楚了。但如果您想要解决问题，可以在这里找到Geeks for Geeks它可以很好地解释您的问题。

Answer 2

没有任何关于你的输入的假设，在O(n)时间和O(1)空间没有办法做到这一点

• 拥有O(1)空间意味着您可以预先确定要分配的空间量。意味着它是常量（因此不依赖于您的基础数组）
• 如果您可以将输入限制为某个集合，则可以实现。一些例子是 当你得到一个包含char的the ASCII charset数组时，你就可以将你的空间固定为128个integers数组。然后迭代输入并增加arr[charCode(currentChar)]中的数字 一系列的positive intergers。您可以创建一个大小为Integer.MAX_VALUE的整数数组，即2^32 - 1。然后应用与以前相同的逻辑。

Answer 3

我认为在O（1）空间和O（n）时间这样做很难，除非你能做出一些假设，正如其他一些答案所暗示的那样。我不认为分配一个长度为MAXINT的数组真的是正确的选择。

O（唯一值的数量）空间和O（n）的答案要容易得多。使用哈希，其中键是数组中的值，哈希值是计数。您将有一次通过您的数据，然后您有一个完整计数的哈希。

HashMap<Integer,Integer> map.= new HashMap<Integer,Integer>();
for (int value: array) {
   Integer valueI = new Integer(value);
   if (!map.hasKey(valueI)) {
       Integer count = new Integer(1);
       map.put(valueI, count);
   }
   else {
       Integer oldCount = map.get(valueI);
       Integer newCount = new Integer(oldCount.intValue() + 1);
       map.put(valueI, count);
   }
}

这样的事情。地图的键包含唯一值和每个计数的键映射的值。

在没有对数据进行大量假设或分配真正庞大的数组的情况下，我无法想出你在O（1）空间中可以做的任何事情。毕竟，你必须将结果存储在某个地方。