騰訊 百度 面試題

騰訊：

try

finally

百度：

int array[] = {0,1,2,3,4,5,6,7,8,9...};

随機輸出array中的值，并且不能重複,又完整輸出一遍

要求空間複雜度和時間複雜度最小

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Modern method

We'll now do the same thing using Durstenfeld's version of the algorithm: this time, instead of striking out the chosen numbers and copying them elsewhere, we'll swap them with the last number not yet chosen. We'll start by writing out the numbers from 1 to 8 as before. For clarity, we'll use a vertical bar (|) to separate the part of the list that has already been processed from the part that hasn't been permuted yet; of course, no such separator is actually used in the real algorithm:

Range	Roll	Scratch | Result
1 2 3 4 5 6 7 8 |

For our first roll, we roll a random number from 1 to 8: this time it's 6, so we swap the 6th and 8th numbers in the list:

Range	Roll	Scratch | Result
1–8	6	1 2 3 4 5 8 7 | 6

The next random number we roll from 1 to 7, and turns out to be 2. Thus, we swap the 2nd and 7th numbers and move on:

Range	Roll	Scratch | Result
1–7	2	1 7 3 4 5 8 | 2 6

The next random number we roll is from 1 to 6, and just happens to be 6, which means we leave the 6th number in the list (which, after the swap above, is now number 8) in place and just move to the next step. Again, we proceed the same way until the permutation is complete:

Range	Roll	Scratch | Result
1–6	6	1 7 3 4 5 | 8 2 6
1–5	1	5 7 3 4 | 1 8 2 6
1–4	3	5 7 4 | 3 1 8 2 6
1–3	3	5 7 | 4 3 1 8 2 6
1–2	1	7 | 5 4 3 1 8 2 6

At this point there's nothing more that can be done, so the resulting permutation is 7 5 4 3 1 8 2 6.