ThinkChat2.0新版上线,更智能更精彩,支持会话、画图、阅读、搜索等,送10W Token,即刻开启你的AI之旅 广告
《编程珠玑》习题1.4:如果认真考虑了习题3,你将会面对生成小于n且没有重复的k个整数的问题。最简单的方法就是使用前k个正整数。这个极端的数据集合将不会明显的改变位图方法的运行时间,但是可能会歪曲系统排序的运行时间。如何生成位于0至n - 1之间的k个不同的随机顺序的随机整数?尽量使你的程序简短高效。 如下的程序产生1-n的不重复的随机数: ~~~ void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } void produce (int a[], int n) { int i; //对数组a依次赋一个不同的值 for (i = 0; i < n + 1; i++) { a[i] = i + 1; } srand((int)time(0)); //下面的语句用于产生n个不同的随机数,存于数组的0到n-1位中 // i + rand() % (n - i)产生一个范围i到n的随机数 //那么将这个下标的数组数据和以i为下标的数组数据swap肯定不重复 for (i = 0; i < n; i++) { swap(&a[i], &a[i + rand() % (n - i)]); } } ~~~ 上面的算法复杂度为O(n); 在文章[Libnids的哈希函数](http://blog.csdn.net/u013074465/article/details/45061605)中,libnids的void init_hash () 函数也提供了一种产生0到11之间不重复随机数的方法,其复杂度为O(n ^ 2). 参考: [http://blog.chinaunix.net/uid-21228455-id-2406483.html](http://blog.chinaunix.net/uid-21228455-id-2406483.html) [http://blog.csdn.net/wdzxl198/article/details/12000091](http://blog.csdn.net/wdzxl198/article/details/12000091)