使用框架的Random
类,我想出了以下懒惰的实现来洗牌一副牌。
我估计下面的代码的最坏情况复杂度为O(n+nLogn)。我说得对吗?
数据结构
enum SuitType
{
Diamond,
Heart,
Spade,
Club
}
class Card
{
public SuitType suitType;
public int value;
public int randomOrder;
}
我为每张卡片添加了一个可变的随机顺序。
然后我使用randome.next()为每张卡获取一个随机数。
根据这个随机数对牌组进行排序。
class Program
{
static void Main(string[] args)
{
Program p = new Program();
List<Card> deck = new List<Card>(52);
p.InitializeDeck(deck);
List<Card> shuffledDeck = p.ShuffleDeck(deck).ToList();
}
Random r = new Random();
readonly int RMIN = 1, RMAX = 100;
//O(N + NlogN)
private IEnumerable<Card> ShuffleDeck(List<Card> deck)
{
//O(N)
foreach (var d in deck)
{
d.randomOrder = r.Next(RMIN, RMAX);
}
//O(NlogN)
return deck.OrderBy(d => d.randomOrder);
}
private void InitializeDeck(List<Card> deck)
{
int suitCounter = 0;
for (int i = 1; i <= 52; i++)
{
deck.Add(new Card
{
suitType = (SuitType)suitCounter,
value = i,
randomOrder = r.Next(RMIN, RMAX)
});
if (i % 13 == 0)
{
suitCounter++;
}
}
}
}
最佳答案
你可以用
return deck.OrderBy(d => r.Next());
这可能不影响算法的复杂性,但它使方法更简单。
更新:
我的观点是,用大O符号来思考在这里是不相关的,除非你不得不洗牌数百万的甲板,并发现性能确实是一个问题。