c++ - 随机往数组中插入1-100的数字

Question

今天面试遇到的题，题目要求，往a[100]中插入1-100的数字，要求每个数字都不同且无规律。

我说了两种思路，然后第一种方法，初始化a[100]={0},然后每生成一个随机数与之前插入的数字比较，如果相同则重新生成，时间复杂度为n*n,然后面试官这个不够高效，他说插入最后一个元素时你可能要随机生成多次。

然后我昨天看了下stl里的东西，set里布允许有重复元素，所以我想到了思路二，可以生成随机数往set里插入，当set的size()到100时停止，然后我刚写得代码如下，结果却不是我想要的结果。

int main()
{
    set<int> nums;
    srand((unsigned int)time(nullptr));
    while(nums.size()<100)
    {
       
        nums.insert(random()%100+1);
    }
    
    
    for(auto &i:nums)
        cout<<i<<" ";
    return 0;
}

输出结果为：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

生成种子放在while内和while外都是一个结果，跪求分析程序的问题所在.

Answer 1

有个问题叫做“完美洗牌”，意思是说，一副牌去掉大小王还剩52张，现在要洗这52张牌。显然，洗牌共有52!种结果。完美洗牌要求52!种洗牌结果出现的概率相同。

有没有感觉很像？这道面试题要求数字分布“无规律”，也就是要求每种结果出现的概率满足随机均匀分布。所以这道题目相当于完美洗牌，只不过要洗100张牌。

简单起见，以5张牌为例：A, B, C, D, E，问题是，能否在完美洗前4张牌的基础上，把战果扩大为完美洗5张牌呢？如果可以，那么我们就可以用迭代或者递归解决完美洗牌问题。幸好，答案真的是“可以”。

假设A, B, C, D已经实现了完美洗牌，现在来了第5张牌E，可以在A, B, C, D中随机挑选一张牌，即rand(0, 3)，然后将这张牌和E交换，于是这5张牌就实现了完美洗牌。

用C++解决这道题目：

#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iostream>

void shuffle(int *arr, int n) {
  assert(arr && n > 0);
  for (int i = 0; i < n; ++i) {
    int r = rand() % (i + 1);
    int temp = arr[r];
    arr[r] = arr[i];
    arr[i] = temp;
  }
}

int main() {
  int arr[100];
  for (int i = 0; i < 100; ++i) {
    arr[i] = i + 1;
  }
  srand(time(NULL));
  shuffle(arr, 100);
  for (int i = 0; i < 100; ++i) {
    std::cout << arr[i] << ' ';
    if ((i + 1) % 10 == 0) {
      std::cout << std::endl;
    }
  }
  return 0;
}

结果如下所示：

4 51 11 58 14 81 67 25 61 57 
76 22 34 12 98 16 45 55 100 89 
37 88 15 75 99 73 96 66 63 54 
8 83 1 93 42 48 86 85 9 71 
6 59 40 46 31 19 17 53 7 29 
13 2 32 56 74 52 60 30 26 77 
38 64 33 3 50 78 43 21 47 97 
62 69 72 92 10 27 24 28 79 87 
5 36 65 90 91 35 20 80 70 23 
39 41 84 82 94 49 95 68 44 18 

Answer 2

1. 初始化一个从1~100的数组

2. 从0~99循环，每次生成一个0~99的随机数n，将当前数组元素与第n个元素交换
   结果就是需要的随机数组

谁踩的，来来来，敢不敢来咱们探讨一下人生！http://codepad.org/TPoDUiQV

Answer 3

对m-n随机排序可以用random_shuffle

  using namespace std;

  vector<int> vec;
  generate_n(back_inserter(vec), 100, [i = 0]() mutable {
    return i++;
  });
  random_shuffle(begin(vec), end(vec));
  copy(begin(vec), end(vec), ostream_iterator<int>(cout, " "));

set容器是有序容器，遍历的时候是已经排序了的，所以用set是不行的，除非使用自定义比较，在自定义比较中实现随机排序

Answer 4

set 不能插入重复数据 nums.insert(1) 再 nums.insert(1)，它的 size 为 1，而你要它 size 为 100 才停，那么停下来时肯定是 100 个不一样的数据。

set 的迭代不像 array ， 它不一定是按 insert 的顺序来的，看内部实现，可以是从 小 到 大的，所以就这样了

Answer 5

简单来说是洗牌算法
抄袭一个

for i:=1 to n do 
   swap(a[i], a[random(i,n)]);
//random生成 [i,n] 的随机数（包括i和n），数组下标从1开始

证明（但是他的证明是逆序遍历的）：http://www.gocalf.com/blog/shuffle-algo.html

Answer 6

洗牌知道吧，先按顺序1-100存到数组，在随机交换多次（就像洗牌一样）比如交换20次，就可以打乱

Answer 7

这个在算法导论上也是有讲的，就不造轮子了，直接截图：

Answer 8

一个最简单的方法，你先初始化一个1-100的数组，然后调用std::sort。你会发现这个函数需要让你传入一个仿函数对向来比较两个数字的大小，你只需要每次返回随机结果就可以了。特别简单粗暴。

Answer 9

NSMutableArray *array = [NSMutableArray array];
[array addObject:@1];
for (int i = 2; i < 101; i ++) {
    NSInteger num = arc4random()%array.count;

    [array insertObject:[NSNumber numberWithInteger:i] atIndex:num];
}
NSLog(@"%@",array);