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

There is a problem called "perfect shuffling", which means that there are 52 cards left in a deck of cards after removing the kings and kings, and now these 52 cards need to be shuffled. Obviously, there are 52! possible outcomes for shuffling the cards. Perfect shuffling requires that 52! shuffle results have the same probability of occurring.

Do you feel similar? This interview question requires that the number distribution is "irregular", which means that the probability of each outcome satisfies a random uniform distribution. So this question is equivalent to a perfect shuffle, except that 100 cards have to be shuffled.

For the sake of simplicity, let’s take 5 cards as an example: A, B, C, D, E. The question is, based on the perfect shuffling of the first 4 cards, can the result be expanded to a perfect shuffling of 5 cards? If possible, then we can use iteration or recursion to solve the perfect shuffle problem. Fortunately, the answer really is "yes."

Assume that A, B, C, and D have been perfectly shuffled, and now the fifth card E comes. You can randomly select a card among A, B, C, and D, that is, rand(0, 3) , and then exchange this card with E, so these 5 cards are perfectly shuffled.

Use C++ to solve this problem:

#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;
}

The result looks like this:

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. Initialize an array from 1 to 100

2. Loop from 0 to 99, generate a random number n from 0 to 99 each time, and exchange the current array element with the nth element
   The result is the required random array

Who stepped on it, come on, come on, do you dare to come and let’s discuss life! http://codepad.org/TPoDUiQV

Answer 3

You can use random_shuffle

to randomly sort m-n

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

The set container is an ordered container, and it is already sorted when traversing, so it is not possible to use set, unless you use a custom comparison to implement random sorting in the custom comparison

Answer 4

set cannot insert duplicate data nums.insert(1) and then nums.insert(1), its size is 1, and you want it to stop when size is 100, then there must be 100 different data when you stop. .

The iteration of

set is not like array. It is not necessarily in the order of insert. Looking at the internal implementation, it can be from small to large, so that’s it

Answer 5

Simply speaking, it is a shuffling algorithm
Plagiarism

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

Proof (but his proof is traversal in reverse order): http://www.gocalf.com/blog/shuffle-algo.html

Answer 6

You know how to shuffle the cards, first save them into the array in order 1-100, and then randomly exchange them multiple times (just like shuffling the cards), for example, exchange 20 times, you can disrupt it

Answer 7

This is also discussed in the introduction to algorithms, so I won’t reinvent the wheel and just take a screenshot:

Answer 8

The simplest method is to initialize an array of 1-100 and then call std::sort. You will find that this function requires you to pass in a functor pair to compare the size of two numbers, and you only need to return a random result each time. Very simple and crude.

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);