首页 > 代码库 > 《Cracking the Coding Interview》——第18章:难题——题目2
《Cracking the Coding Interview》——第18章:难题——题目2
2014-04-29 00:59
题目:设计一个洗牌算法,效率尽量快点,必须等概率。
解法:每次随机抽一张牌出来,最后都抽完了,也就洗好了。时间复杂度O(n^2),请看代码。
代码:
1 // 18.2 shuffle a deck of 52 cards, it must be perfect random. 2 #include <cstdio> 3 #include <cstdlib> 4 #include <ctime> 5 #include <vector> 6 using namespace std; 7 8 void printCards(const vector<int> &cards) 9 { 10 int i; 11 int n = (int)cards.size(); 12 const int col = 8; 13 14 for (i = 0; i < n; ++i) { 15 printf((i % col == col - 1 ? "%4d\n" : "%4d "), cards[i]); 16 } 17 printf("\n"); 18 } 19 20 void shuffleCards(vector<int> &cards) 21 { 22 vector<int> v; 23 24 v = cards; 25 int i, j; 26 int n, n0; 27 int idx; 28 29 n0 = n = (int)cards.size(); 30 for (i = 0; i < n0; ++i) { 31 idx = rand() % n; 32 cards[i] = v[idx]; 33 --n; 34 for (j = idx; j < n; ++j) { 35 v[j] = v[j + 1]; 36 } 37 } 38 39 v.clear(); 40 } 41 42 int main() 43 { 44 srand((unsigned)time(NULL)); 45 vector<int> cards; 46 int i; 47 const int n = 52; 48 49 cards.resize(n); 50 for (i = 0; i < n; ++i) { 51 cards[i] = i; 52 } 53 54 shuffleCards(cards); 55 printCards(cards); 56 57 return 0; 58 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。