A deck of cards is represented by an integer array of size 52, with possible value of 1 - 13 for each position. Design an algorithm to shuffle the deck of cards in linear time, in-place.
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
April 26, 2016
http://www.geeksforgeeks.org/shuffle-a-given-array/
“shuffle a deck of cards” or “randomize a given array”
Question and answer:
1. Understand the naive approach, extra space - an array, and also time O(n^2).
2. Came cross this blog <- So, use Fisher-Yates algorithm
大概就是取一个array里的任意n个不同的值,得到一个随机的组合，不能取同一个index的数，但是可以取数值相同的不同index的数
给一个array：[5,1,3,3],
再给一个数字n：2，
求这个array里的任意num个数：比如可以得到[5,1] or [5,3] or [1,3] or [3,3] ，但是不能得到[5,5]
再比如[5,1,3,3], 1 ===> [5] or [1] or [3]
就是先判断如果n>array.length或者n<=0或者array是空,返回一个空array
否则就是一个loop，每一次生成一个random的index数字，还用了一个hashset来存之前访问过的index，如果生成的random index之前已经get了，就再继续生成一个random index。
loop n次，每次取到的值放进新的结果array里。.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
然后说了说也可以用一个boolean array存每个值有没有已经取到。。
写完后再写了写unit test什么的，还有问道怎么检测得到的结果比如[5,1]确实是[5,1,3,3]里的
Julia's comment:
3 issues:
1. In place - no extra array
2. Hashset is also extra memory
3. Work on array index - random number selection using % operator, not on value in the array.
3. Let us walk through the code and then add comments - make it fun memory:
// A function to generate a random permutation of arr[]void randomize ( int arr[], int n ) { // Use a different seed value so that we don't get same // result each time we run this program srand ( time(NULL) ); // Julia, Good to know, C++, look up srand API // Start from the last element and swap one by one. We don't // need to run for the first element that's why i > 0 for (int i = n-1; i > 0; i--) { // Pick a random index from 0 to i int j = rand() % (i+1); // Julia: random number -> Range (0, i) using module // Swap arr[i] with the element at random index swap(&arr[i], &arr[j]); // swap two nodes }
No comments:
Post a Comment