获取不重复的随机数列（打乱一组连续数列的顺序）的未解之谜

这个问题面试的时候被问到过，之前的思路是这样的：1，生成1-->N的数组Array。2，Radom出一个num,0<=num<N，3，每个位置的数都跟num交换，知道最后一个数，输出数组Array。如下：

public int[]getRadomSequence(int total) {

int[] output =new int[total];

    for (int i =0; i < total; i++) {

output[i]=i;

    }

Random random =new Random();

    //获取随机数

    int num = random.nextInt(total);

    for(int i=0;i

//所有位置的数与随机位置的数交换

        int t =output[i];

        output[i]=output[num];

        output[num]=t;

    }

return output;

}

然后，面试的人说，你这个效率不行啊。也没说原因，我感到很奇怪，我觉两个循环，一个循环，生成有序数列，另外一个循环交换生成随机数列，算起来是O(n)。后来我在网上看到很多人给出的是如下：

public int[]getRadomSequenceI(int total) {

int[] hashTable =new int[total];

    int[] output =new int[total];

    Random random =new Random();

    for (int i =0; i < total; i++) {

int num = random.nextInt(total);

        while (hashTable[num] >0) {

num = random.nextInt(total);

        }

output[i] = num;

        hashTable[num]=1;

    }

return output;

}

这个我就奇怪了，这个是循环套循环的，时间复杂度外层O(n)，内层O(logn),算起来是O(nlogn)，那不是不如我的？

后来我看到了一个改进型的算法：

public int[]getRadomSequenceII(int total) {

int[] sequence =new int[total];

    int[] output =new int[total];

    for (int i =0; i < total; i++) {

sequence[i]=i;

    }

Random random =new Random();

    int end=total-1;

    for(int i=0;i< total ;i++){

int num = random.nextInt( end +1);

        output[i] = sequence[num];

        sequence[num] = sequence[end];

        end--;

    }

return output;

}

这个算法，前一半跟我的一样，后一半是把随机的位置的数给将要输出的随机数列，然后缩短随机数的取值范围，直到最后，算起来时间复杂度也是O(n)，我只用了一个数组，这里还用了两个数组，空间复杂度算是我的两倍，不解，有大神可以在下面回复，万分感谢！