输入: 一个包含整数值1到N(某些整数值可以出现多次!)的只读长度为N的数组和一个固定大小(10,100,1000等 - 不取决于 N)的内存区域。
如何在O（n）的时间复杂度下确定该数组是否表示排列？
--到目前为止我所获得的（一个答案证明这是不好的）：
我知道如果条件（2）成立，我可能会有一个排列。 我想知道是否有办法证明条件（2）足以告诉我是否有一个排列。 到目前为止，我还没有弄清楚...
根据您相对于N的可用空间大小，您可以尝试使用哈希和桶。
也就是说，遍历整个列表，对每个元素进行哈希处理，并将其存储在一个桶中。您需要找到一种方法来减少哈希冲突，但这是一个已经解决的问题。
如果一个元素试图进入一个与它相同的项目的桶中，那么它就是一个排列。
这种类型的解决方案将是O(N)，因为您只会一次接触每个元素。
然而，这种方法的问题在于M是否大于N。如果M > N，则此解决方案将很好，但如果M < N，则您将无法以100％的准确度解决问题。
求和与乘积不能保证正确答案，因为这些哈希值可能会发生冲突，即不同的输入可能会产生相同的结果。如果您想要一个完美的哈希值，即一个单一数字结果，它实际上完全描述了数组的数值组成，那么可以采用以下方法。
假设对于范围在[1, N]内的任何数字i，您都可以生成一个唯一的质数P(i)（例如，P(i)是第i个质数）。现在，您需要做的就是计算所有数字的P(i)的乘积。该乘积将完全且明确地描述您的数组的组成，而不考虑其中的值的顺序。您只需要预先计算出“完美”值（对于排列），并将其与给定输入的结果进行比较即可 :)
当然，像这样的算法并不能立即满足发布的要求。但同时它又太过通用：它允许您检测数组中绝对任何数字组合的排列。在您的情况下，您需要检测特定组合1, 2, ..., N的排列。也许这可以用来简化事情... 可能不行。
看起来是要使用堆栈机在数组中查找重复项。
当你提取每个数字并且对于被取出的数字有限的了解时，似乎不可能知道堆栈的完整历史记录。
这里有证据表明它是不可能完成的：
假设通过某种手段，你已经在除了最后一个单元格之外的所有单元格中检测到了没有重复项。那么问题就简化为检查最后一个单元格是否包含重复项。
如果你目前没有结构化的问题状态表示，那么你只能对每个单元格执行整个先前输入的线性搜索。很容易看出，这会让你得到一个二次时间算法。
现在，假设通过一些聪明的数据结构，你实际上知道了你期望看到的最后一个数字。那么肯定需要至少足够的位数来存储你要寻找的数字——也许是一个内存单元？但是还有倒数第二个数字和倒数第二个子问题：然后你必须类似地表示一组尚未看到的两个可能的数字。这肯定需要比仅编码一个剩余数字更多的存储空间。通过类似的论证进展，状态的大小必须随着问题的规模增长，除非你愿意接受二次时间最坏情况。
这就是时间和空间的权衡。你可以拥有二次时间和恒定空间，或者线性时间和线性空间。你不能同时拥有线性时间和恒定空间。
int solution(int A[], int N) {
int i,j,count=0, d=0, temp=0,max;
for(i=0;i<N-1;i++) {
for(j=0;j<N-i-1;j++) {
if(A[j]>A[j+1]) {
temp = A[j+1];
A[j+1] = A[j];
A[j] = temp;
}
}
}
max = A[N-1];
for(i=N-1;i>=0;i--) {
if(A[i]==max) {
count++;
}
else {
d++;
}
max = max-1;
}
if(d!=0) {
return 0;
}
else {
return 1;
}
}
N!所需的存储空间，严格来说取决于N。而且严格来说，在O(N)的时间内无法对N个数字进行乘法运算。 - polygenelubricantsm个数中的n个，并停止了你的算法。现在你可以（虽然需要一些时间）通过处理任何一个由n-m个数字组成的流并查看何时出现排列来确定你已经看到了哪m个数字。因此从信息的角度来看，你已经存储了所有的数字m，因此必须使用线性内存。 - Thomas Ahle