C语言生成不重复随机数的高效方法

实现原理与目标

我们需要生成的是一组包含 N 个元素的数组，元素值为 [1, N] 之间的整数且互不相同。直接随机抽取容易导致冲突检测耗时过长。本方案采用“以空间换时间”的策略：

1. 创建一个辅助数组 pfrom，初始化为 [1, 2, ..., N]。

2. 每次随机选取 pfrom 中的一个位置 index。

3. 如果该位置未被标记为已使用（值不为0），则将其值复制到结果数组，并将 pfrom[index] 置为0表示已取走。

4. 重复上述过程直到结果数组填满。

这种方法保证了每个数字被选中的概率均等，且只需单次遍历即可完成，时间复杂度稳定为 O(N)。

完整代码实现

以下是完整的函数实现。注意：srand(time(0)) 用于初始化随机种子，确保每次运行程序生成的序列不同。请在主函数中调用此种子初始化函数，或在首次调用前执行。

void diffarr(int arr[], int n)
{
    // sn记录剩余待填充的数量，ptr指向结果数组起始位置
    int sn = n, index, *ptr = arr;
    
    // 动态分配辅助数组，初始化为 1 到 n
    int *pfrom = new int[sn];
    for (int i = 0; i < sn; i++)
        *(pfrom + i) = i + 1;
    
    // 初始化随机数种子（注：实际工程中建议在main中只调用一次）
    srand((unsigned int)time(NULL));
    
    // k为结果数组当前写入位置
    for (int k = 0; k < sn; )
    {
        // 随机选择一个索引
        index = rand() % sn;
        
        // 如果该位置未被占用（值不为0）
        if (*(pfrom + index) != 0)
        {
            // 将值放入结果数组
            *(ptr + k) = pfrom[index];
            // 标记该位置已使用
            pfrom[index] = 0;
            // 结果数组指针后移
            k++;
        }
    }
    
    // 释放辅助数组内存
    delete[] pfrom;
}

关键参数说明

• arr[]：输出数组，用于存储生成的不重复随机数。
• n：随机数的个数，同时也决定了数值范围（1 到 n）。
• srand(time(0))：设置随机种子。若需在不同位置多次生成不同序列，可修改种子逻辑。

性能与注意事项

相较于暴力法（Random-then-check），本算法在任何情况下都能保证 O(N) 的时间复杂度，且没有复杂的哈希冲突处理开销。但需要注意内存管理：new int[sn] 分配的内存必须在函数结束前通过 delete[] 释放，否则会造成内存泄漏。
此外，对于极小的 N，此开销可忽略；当 N 较大时，这种线性扫描依然高效。若需生成极大范围的随机数，需考虑是否需要调整数据类型以防止溢出。

以上就是利用C/C++生成一组不同随机数的详细内容，更多关于C语言随机算法的资料请关注本站其它相关文章！