整数的随机置换

算法描述:生成前N个整数的随机置换，如{4,3,1,5,2}，{4,5,3,2,1}是合法的，而{5,4,1,1,2}不合法，因为3没出现。

1.基本算法

该算法效率比较低，O(n*n*logn)，主要就是随机的生成一个数，然后再一直数组中去检测是否存在，如果不存在才插入。从而效率低下

 

//使用的是思想1(O(n*n*logn))
int* getRandom(int* a, int length){
		for(int i=0; i<length; i++){
			int j = randInt(0, length);
			//循环，直到找到一个在数组中不存在的值,这里的复杂度是n*logn
			while(true){
				if(findExist(a, i, j)){
					j = randInt(0, length);
				}else{
					break;
				}
			}
			a[i] = j;
		}
		return a;
}

 2.对算法1进行了改进，主要就是增加了一个标志数组，对于已经使用过的数进行了标记，从而不用再遍历原数组，复杂度O(n*logn)降低了不少，但以空间换时间

 

//使用思想2(O(n*logn))
int* getRandom2(int* a, const int length){
		int used[LEN] = {0};
		for(int i=0; i<length; i++){
			int j = randInt(0, length);
			//循环，直到找到一个在数组中不存在的值
			while(used[j]){
				j = randInt(0, length);
			}
			used[j] = 1;
			a[i] = j;
		}
		return a;
}

 

 

3.使用了逆向思维，为什么我们不一次性插入所有数据，然后再随机交换位置，从而达到此效果呢？该算法就是这样，复杂度O(n)，线性的

 

//使用思想3(O(n))
int* getRandom3(int* a, const int length){
		int i;
		//初始化0-9
		for(i=0; i<length; i++){
			a[i] = i;
		}
		//任意交换位置，打乱次序
		for(i=0; i<length; i++){
			int temp = a[i];
			int j = randInt(0, i);
			a[i] = a[j];
			a[j] = temp;
		}
		return a;
}

 

 从1-3就是一个算法改进的过程体现，不断的减少时间复杂度，空间消耗，从而实现一个优秀的算法所必须的过程。

 

4.全部代码

 

#include <iostream>
#include <cstdlib>
#include <time.h>//用于做种子
const int LEN = 1000;
using namespace std;

int randInt(int start, int end){
	return start+(end-start)*rand()/(RAND_MAX + 1.0);
}

int findExist(const int* a, int length, int value){
	for(int i=0; i<length; i++){
		if(a[i] == value) return true;
	}
	return false;
}

//使用的是思想1(O(n*n*logn))
int* getRandom(int* a, int length){
		for(int i=0; i<length; i++){
			int j = randInt(0, length);
			//循环，直到找到一个在数组中不存在的值,这里的复杂度是n*logn
			while(true){
				if(findExist(a, i, j)){
					j = randInt(0, length);
				}else{
					break;
				}
			}
			a[i] = j;
		}
		return a;
}


//使用思想2(O(n*logn))
int* getRandom2(int* a, const int length){
		int used[LEN] = {0};
		for(int i=0; i<length; i++){
			int j = randInt(0, length);
			//循环，直到找到一个在数组中不存在的值
			while(used[j]){
				j = randInt(0, length);
			}
			used[j] = 1;
			a[i] = j;
		}
		return a;
}

//使用思想3(O(n))
int* getRandom3(int* a, const int length){
		int i;
		//初始化0-9
		for(i=0; i<length; i++){
			a[i] = i;
		}
		//任意交换位置，打乱次序
		for(i=0; i<length; i++){
			int temp = a[i];
			int j = randInt(0, i);
			a[i] = a[j];
			a[j] = temp;
		}
		return a;
}


int main(){
//	srand(unsigned(time(0)));//,随机数种子,使用这个就可以每次不同
	int a[LEN] = {0};
	srand(time(NULL));
//	int *b = getRandom(a, LEN);
//	int *b = getRandom2(a, LEN);
	int *b = getRandom3(a, LEN);
	for(int i=0; i<LEN; i++){
		cout<<b[i]<<" ";
	}
	return 0;	
}