C++生成不重复随机数的方法

2013-12-26 21:20:17   4725

在做洗牌算法的时候用到了随机数,并且产生的随机数中不能有重复的元素,因为是用C语言实现的,就把值赋给数组,然后用随机数产生数组的下标,每产生一个就删除对应的元素,然后随机数的生成范围减一,但是这样做每次都要循环去移动数组元素,从时间复杂度上来说这样并不好。


于是,后来用C++重新实现:实现的思路并没有变,只是把数组换成了容器,因为STL有删除元素的操作,所以就减少了循环的使用

vector<int> getRandom(int total)
{
    srand((int)time(NULL));
    std::vector<int> input = *new std::vector<int>();
    for (int i = 0; i < total; i++) {
        input.push_back(i);
    }
    vector<int> output = *new vector<int>();
    
    int end = total;
    for (int i = 0; i < total; i++) {
        vector<int>::iterator iter = input.begin();
        int num = random()%end;
        iter = iter+num;
        output.push_back(*iter);
        input.erase(iter);
        end--;
    }
    
    return output;
}


上一篇:C++ set用法实战

下一篇:C++学习杂记