《编程珠玑》习题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)
- 前言
- Josephus约瑟夫问题及其变种
- 链表的常见实现
- 二叉树遍历、插入、删除等常见操作
- 二叉堆的插入删除等操作C++实现
- 插入排序和希尔排序
- 堆排序
- 归并排序及其空间复杂度的思考
- 快速排序的几种常见实现及其性能对比
- 红黑树操作及实现
- 整数的二进制表示中1的个数
- 位操作实现加减乘除四则运算
- 冒泡排序的改进
- 直接选择排序
- 不借助变量交换两个数
- 基础排序算法总结
- AVL树(Adelson-Velskii-Landis tree)
- avl树的C++实现
- 动态规划之钢条分割
- hash函数的基本知识
- 动态规划:求最长公共子串/最长公共子序列
- 最长递增子序列
- 称砝码问题
- 汽水瓶
- 字符串合并处理(二进制位的倒序)
- 动态规划:计算字符串相似度
- m个苹果放入n个盘子
- 生成k个小于n的互不相同的随机数
- 栈和队列的相互模拟
- 字符串的排列/组合
- KMP(Knuth-Morris-Pratt)算法
- n个骰子的点数
- 位运算的常见操作和题目