时间空间复杂度问题 求详解？？

Question

有一个长为N的数组里放着【1，N】范围的整数，设计一个算法判断这些整数有没有重复的。你的算法的时间空间复杂度各是多少？

Answer 1

判断这些整数有没有重复
只需要判断?最容易想到的算法:array[N];
[N] = {0};
for(i = 0; i < N; ++i)
{
if([array[i]-1] == 0)
++[array[i]-1];
else
{
有重复;
break;
}
}时间复杂度N空间复杂度N

Answer 2

最容易想到用两个for循环,例如array[n];
for(int i=0; i<n-1; i++){
   for(int j=i+1;j<n;j++){
      if(array[i]==array[j]){
          System.out.println('有重复');
          break;
      } 
  }
}那么此时的时间复杂度为n*n/2,空间复杂度为n-------------------------------------若采用类似标记的方法的话
如三楼的思路，应该空间复杂度为2n,时间复杂度为n吧

Answer 3

n和2n，3n，4n，5n，6n都是说的一个数量级的，记得在数据结构里都用等阶无穷小O(n)表示吧~

Answer 4

新建一个数组，用来表示1~N中每个数字出现的次数，然后遍历给定的数组，统计数组中数字出现的次数，当判断条件不成立的时候，就表示array[i]这个数字之前已经出现过了，现在又出现了一次，所以判断有重复，break结束。