這個問題面試的時候被問到過逮栅，之前的思路是這樣的：1，生成1-->N的數(shù)組Array窗宇。2措伐，Radom出一個num,0<=num<N，3军俊，每個位置的數(shù)都跟num交換侥加，知道最后一個數(shù)，輸出數(shù)組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();
? ? //獲取隨機數(shù)
? ? int num = random.nextInt(total);
? ? for(int i=0;i
//所有位置的數(shù)與隨機位置的數(shù)交換
? ? ? ? int t =output[i];
? ? ? ? output[i]=output[num];
? ? ? ? output[num]=t;
? ? }
return output;
}
然后担败，面試的人說，你這個效率不行啊镰官。也沒說原因提前，我感到很奇怪，我覺兩個循環(huán)泳唠，一個循環(huán)狈网，生成有序數(shù)列，另外一個循環(huán)交換生成隨機數(shù)列笨腥，算起來是O(n)孙援。后來我在網(wǎng)上看到很多人給出的是如下：
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;
}
這個我就奇怪了，這個是循環(huán)套循環(huán)的扇雕，時間復雜度外層O(n)拓售，內(nèi)層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;
}
這個算法础淤，前一半跟我的一樣崭放，后一半是把隨機的位置的數(shù)給將要輸出的隨機數(shù)列，然后縮短隨機數(shù)的取值范圍鸽凶，直到最后币砂，算起來時間復雜度也是O(n)，我只用了一個數(shù)組玻侥，這里還用了兩個數(shù)組决摧，空間復雜度算是我的兩倍，不解凑兰，有大神可以在下面回復掌桩，萬分感謝！
