生成k个小于n的互不相同的随机数

谁践踏了优雅 2022-08-01 01:17 137阅读 0赞

《编程珠玑》习题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的哈希函数][Libnids]中，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]

[Libnids]: http://blog.csdn.net/u013074465/article/details/45061605
[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