输入: 一个包含整数值1到N(某些整数值可以出现多次!)的只读长度为N的数组和一个固定大小(10,100,1000等 - 不取决于 N)的内存区域。
如何在O(n)的时间复杂度下确定该数组是否表示排列?
--到目前为止我所获得的(一个答案证明这是不好的):
- 我使用有限的内存区域来存储数组的总和和乘积。
- 我将总和与N *(N + 1)/ 2进行比较,将乘积与N!进行比较。
我知道如果条件(2)成立,我可能会有一个排列。 我想知道是否有办法证明条件(2)足以告诉我是否有一个排列。 到目前为止,我还没有弄清楚...
N!
所需的存储空间,严格来说取决于N
。而且严格来说,在O(N)
的时间内无法对N
个数字进行乘法运算。 - polygenelubricantsm
个数中的n
个,并停止了你的算法。现在你可以(虽然需要一些时间)通过处理任何一个由n-m
个数字组成的流并查看何时出现排列来确定你已经看到了哪m
个数字。因此从信息的角度来看,你已经存储了所有的数字m
,因此必须使用线性内存。 - Thomas Ahle