洗牌算法

突然想起来之前面试的一个问题,洗牌算法怎么洗的又快又随机,当时一下问住了,后面自己复习的时候,发现有两种洗牌算法。
1.从52个数中随机选出一个数作为第一位,然后再从52位数随机选出第二位数且不能与前面的数重复,如果重复则重新选择,这样以此往后选择,直到第52位数
时间复杂度为n2,空间复杂度为n
2.从52个数中随机选出一个数作为第一位,再从剩下的数中随机选择一位,和第二交换,如此,直到第52位数
时间复杂度为n,空间复杂度为0

这个还有其他的解法吗?下次面试不知道还会不会问,不知道还可以咋回答
#题解#
全部评论
T=O(n) S=O(1)已经是最优解 比如Fisher–Yates shuffle
点赞 回复 分享
发布于 2019-07-08 16:02

相关推荐

ResourceUtilization:差不多但是估计不够准确,一面没考虑到增长人口,另一方面也没考虑到能上大学的人数比例,不过我猜肯定只多不少
点赞 评论 收藏
分享
04-08 10:36
已编辑
华南理工大学 C++
点赞 评论 收藏
分享
评论
点赞
9
分享

创作者周榜

更多
牛客网
牛客企业服务