如何优化生成无重复数字数组的C++程序以提升运行速度？

你的代码在生成无重复元素数组时速度慢，主要是几个关键逻辑问题导致的，下面分析瓶颈并给出优化方案：

原代码的性能问题 #

• 重复重置随机数种子：每次进入while循环都调用srand，而time(NULL)是秒级更新，短时间内多次调用会让随机数生成器反复重置，导致生成的随机数完全相同，碰撞概率飙升。
• 冗余的重复检查：检查重复时遍历整个数组，但实际上只有前i个元素是已经赋值的有效元素，后面的未初始化元素完全没必要遍历；而且找到重复后不立即终止循环，做了无用功。
• 高碰撞下的无效循环：当arrScale接近10（你的随机数范围是0-9）时，剩下的可用数字越来越少，程序会陷入大量无效的while循环尝试，耗时急剧增加。

优化方案一：洗牌法（最优，适合小范围数字） #

既然你的随机数固定是0-9，直接生成包含所有数字的数组，再打乱顺序取前arrScale个元素，完全避免重复检查，时间复杂度O(n)。

void generateArr() {
    int temp[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int total = sizeof(temp) / sizeof(temp[0]);
    
    // 仅初始化一次随机数种子
    srand((unsigned int)time(NULL));
    
    // Fisher-Yates洗牌算法，高效打乱数组
    for (int i = total - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int swap = temp[i];
        temp[i] = temp[j];
        temp[j] = swap;
    }
    
    // 复制前arrScale个元素到目标数组
    for (int i = 0; i < arrScale; i++) {
        numArr[i] = temp[i];
    }
}

优化方案二：布尔数组快速查重（适合灵活范围） #

如果以后需要调整随机数范围，用布尔数组记录已使用的数字，把查重时间从O(n)降到O(1)，避免冗余遍历。

#include <stdbool.h>

void generateArr() {
    bool used[10] = {false}; // 标记0-9是否已被使用
    srand((unsigned int)time(NULL));
    
    for (int i = 0; i < arrScale; i++) {
        int randomNum;
        // 直到生成未使用的数字
        do {
            randomNum = rand() % 10;
        } while (used[randomNum]);
        
        numArr[i] = randomNum;
        used[randomNum] = true;
    }
}

核心优化点总结 #

• 随机数种子只初始化一次，避免重复重置导致随机数重复。
• 替换低效的数组遍历查重为O(1)的直接检查，或用洗牌法完全避免查重。
• 避免在高碰撞场景下的无限循环尝试，从根源减少无效运算。

内容的提问来源于stack exchange，提问作者DIA_YA