问题：现在有一副扑克牌，随机抽出一张，求抽出的是哪一张牌？给出算法和时间复杂度。
根据题目我做出了如下的结构:
typedef enum Suits {
Spades = 0,
Hearts,
Clubs,
Diamonds,
} Suits;
typedef struct Card
{
Suits suit;
int value;
} Card;
**Suits 代表花色，黑桃、红桃、草花、方块；Card 代表一张牌，value 对应的是牌面的值，也就是 {1, 2, 3, ... , 15} 分别对应 {A, 1, 2, 3 ... J, Q, K , Black Jocker(小王), Red Jocker(大王)}，忽略大王与小王的花色。
小弟愚蠢的思路0：
将牌排序，然后找到少的那一张，也就是经常用的配一变牌，再找。代码规则如下：
做一个 bucket[maxValue][maxSuit + 1] 这样一个桶，遍历抽出后的牌，按照牌面值 value、花色 suit 对应 bucket[value][suit] 的规则，将牌入桶，这样，只要判断前 bucket 桶中的 value 是否等于 0 即可找到抽出的那张牌。
思路0 代码：
Card FindDrewCardFromCards_bucket(Card *cards, int count)
{
Card bucket[15][4] = {0}, drewCard;
int index, jndex;
drewCard.value = 0;
for (index = 0; index < count; index++) {
bucket[cards[index].value - 1][cards[index].suit].suit = cards[index].suit;
bucket[cards[index].value - 1][cards[index].suit].value = cards[index].value;
}
for (index = 0; index < 13; index++) {
for (jndex = 0; jndex < 4; jndex++) {
if (bucket[index][jndex].value == 0) {
drewCard.value = index + 1;
drewCard.suit = jndex;
break;
}
}
}
if (drewCard.value != 0)
return drewCard;
for (index = 13; index < 15; index++) {
if (bucket[index][0].value == 0) {
drewCard.value = index + 1;
break;
}
}
return drewCard;
}
时间复杂度是 O(N)，也就是桶排 + 查找；
大佬们看到可能就笑了，这么做不是疯了么，又复杂又难搞，莫名其妙。
我想说，请原谅小弟的渣代码，而且也确实有点紧张...
下面小弟就给出第二种思路：
**结构还是上面的结构，只不过我们做一个 sum 运算，比如说 “黑桃A” 牌面值为 1， 花色为 Spades = 0，那么“黑桃A” 的值就是 value *** ** 10 + suit = 1, 依次类推， “红桃A” 的值为 2 ... “方块K” 的值为 13 *** ** 10 + 3 = 133，小王的值为 140， 大王的值为 150。按照这个规则，一副完整的牌的值的和为 4008。如果抽出一张 “黑桃5”， 那么剩余的牌的值的和就是 4008 - “黑桃5”的值 = 4008 - 50 = 3958；如果知道了剩余的牌要求出抽出的那张 “黑桃5” 的话，就可以用 4008 - 3958 = 50， 先求出抽出的牌的值， 然后这个值的个位数字就是花色， 这个值除以 10 的值就是牌面的值，我们这里抽出的 “黑桃5” 就可以用 50 % 10 = 0, 得出花色为黑桃， 50 / 10 = 5，得出牌面值为5，就可知道抽出的那张牌就是 “黑桃5” 了。过程很简单，就不列出代码思路了，请直接看代码： **
Card FindDrewCardFromCards_calculate(Card *cards, int count)
{
Card drewCard;
int index, sum;
sum = 0;
for (index = 0; index < count; index++) {
sum += cards[index].value * 10 + cards[index].suit;
}
drewCard.suit = (4008 - sum) % 10;
drewCard.value = (4008 - sum) / 10;
return drewCard;
}
时间复杂度为 O(N)，一次遍历即可得到。
啰嗦了这么多，本篇差不都就到这里，也算是给自己一个交代吧。在此感谢 @sindri的小巢、@戴仓薯 的思路，要不然小弟估计还局限在自己的思维中。
算法与数据结构我也会继续学习下去的，争取三年入门吧。
** 下一篇的话，可能会写一些关于 UI 的东西，也是这次面试遇到的问题。**
本文代码地址：https://github.com/zj159963/FindCard
网友评论