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

Question

今天面试遇到的题，题目要求，往a[100]中插入1-100的数字，要求每个数字都不同且无规律。 我说了两种思路，然后第一种方法，初始化a[100]={0},然后每生成一个随机数与之前插入的数字比较，如果相同则重新生成，时...

PHP中文网 · Answer

有個問題叫做“完美洗牌”，意思是說，一副牌去掉大小王還剩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 
#include 
#include 
#include 

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

初始化一個從1~100的陣列
從0~99循環，每次產生一個0~99的隨機數n，將當前數組元素與第n個元素交換
結果就是需要的隨機數組

誰踩的，來來來，敢不敢來咱們探討一下人生！ http://codepad.org/TPoDUiQV

PHP中文网 · Answer

對m-n隨機排序可以用random_shuffle

  using namespace std;

  vector 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(cout, " "));

set容器是有序容器，遍歷的時候是已經排序了的，所以用set是不行的，除非使用自訂比較，在自訂比較中實現隨機排序

迷茫 · Answer

set 不能插入重複數據nums.insert(1) 再nums.insert(1)，它的size 為1，而你要它size 為100 才停，那麼停下來時肯定是100 個不一樣的數據。

set 的迭代不像 array ，它不一定是按 insert 的順序來的，看內部實現，可以是從小到大的，所以就這樣了

黄舟 · Answer

簡單來說是洗牌演算法
抄襲一個

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

PHPz · Answer

洗牌知道吧，先依序1-100存到數組，在隨機交換多次（就像洗牌一樣）例如交換20次，就可以打亂

巴扎黑 · Answer

這個在演算法導論上也是有講的，就不造輪子了，直接截圖：

高洛峰 · Answer

一個最簡單的方法，你先初始化一個1-100的數組，然後呼叫std::sort。你會發現這個函數需要讓你傳入一個仿函數對向來比較兩個數字的大小，你只需要每次回傳隨機結果就可以了。特別簡單粗暴。

大家讲道理 · Answer