题目要求:随机输出100以内的不重复数字

解法一:暴力求解

最简单也最容易想到的解法:

  1. 创建含有100个元素的数组data[100],全部置零
  2. 生成100以内的随机数r
  3. 如果data[r]等于0,设置data[r]=1
  4. 如果data[r]等于1,重复第二步

此算法的时间复杂度为O(n^2),越到后面,碰撞的机会也越来越大,最坏的情况下,时间复杂度远不止O(n^2)。

解法二:Fisher-Yates shuffle洗牌算法

算法的逻辑为:

  1. 创建一个长度为n的数组(假设下标从1开始),每个元素的值都置为其下标
  2. 设max=n,从n开始到1逐步递减
  3. 生成[1, max]之间的随机数r,把data[r]和data[max]交换,max减一
  4. 重复第三步,直到max小于1

2.1 过程图解

假设要生生十个随机数,创建十个元素的数组,初时时的状态为:

+--+--+--+--+--+--+--+--+--+--+
| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+
                             ^
                            max   

逐步生成随机数的过程:

max = 10, r = 3
        +--------------------+
        v                    v
+--+--+--+--+--+--+--+--+--+--+
| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
                    +-----+
                    v     v
+--+--+--+--+--+--+--+--+--+--+
| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
  +--------------------+
  v                    v
+--+--+--+--+--+--+--+--+--+--+
| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
              +-----+
              v     v
+--+--+--+--+--+--+--+--+--+--+
| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+

...

2.2 代码实现

void shuffle(int *data, int n) {
    int i, r;
    for (i = 0; i < n; i++) {
        data[i] = i;
    }
    for (i = n; i > 0; i--) {
        r = rand() % n;
        swap(&data[r], &data[i - 1]); // 交换
    }
}

单测案例:

TEST(SHUFFLE_TEST, FEATURE_TEST) {
    int i, data[TEST_NODE_COUNT], verify[TEST_NODE_COUNT];
    shuffle(data, TEST_NODE_COUNT);
    memset(verify, 0, sizeof(int) * TEST_NODE_COUNT);
    for (i = 0; i < TEST_NODE_COUNT; i++) {
        verify[data[i]] ++;
    }
    for (i = 0; i < TEST_NODE_COUNT; i++) {
        ASSERT_EQ(verify[i], 1) << verify[i];
    }
}

int main(int argc, char **argv) {
    srand(time(NULL));

    testing::InitGoogleTest(&argc, argv);

    RUN_ALL_TESTS();
    return 0;
}

最后修改:2019 年 04 月 24 日
喜欢就给我点赞吧