问题描述:我在算法作业中发现了这个问题。
它要我找出一个数组中所有元素在O(n)时间和O(1)空间中的频率。
数组可以是
Ar[]={1,6,3,78,4,6,1}
经过思考,我想出了这个办法:
迭代数组并查找max元素。(o(n)time)
创建size=max元素(o(1)空间)的新数组
在原始数组上迭代并在新数组的索引处存储频率(O(n)time)。
我对第二步有疑问。
在步骤1中找到max元素(比如m)之后,我将创建一个m大小的新数组。
事物数组是否占用O(1)空间如果没有请解释
最佳答案
是的,你是正确的,找到最大的数字,然后创建长度的哈希数组并不是O(1)空间复杂度的一种解决方案,因为O(1)空间复杂度指的是一个恒定的空间使用,但是如果你根据输入值来声明数组的大小,那么空间是怎样的一个常数。
常数空间或o(1)复杂度是指不考虑输入值而不依赖输入的方法。
因此,你的这种方法不适合这个解决方案。
希望,我已经说清楚了。
但如果你想解决你的问题,可以在这里找到
Geeks for Geeks
它很好地解释了你的问题。