今天面试遇到的题,题目要求,往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外都是一个结果,跪求分析程序的问题所在.
PHP中文网2017-04-17 13:07:20
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
黄舟2017-04-17 13:07:20
Initialize an array from 1 to 100
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
PHP中文网2017-04-17 13:07:20
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
迷茫2017-04-17 13:07:20
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. .
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
黄舟2017-04-17 13:07:20
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
PHPz2017-04-17 13:07:20
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
巴扎黑2017-04-17 13:07:20
This is also discussed in the introduction to algorithms, so I won’t reinvent the wheel and just take a screenshot:
高洛峰2017-04-17 13:07:20
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.
大家讲道理2017-04-17 13:07:20
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);