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

雷雷