algorithm - 洗牌一堆钥匙

Question

这个问题主要涉及一个著名的面试问题，即洗牌。我浏览了 SO 并发现了类似的问题，但答案大多不符合标准或被忽略。

给出的问题是建立一个洗牌的功能。

我的解决方案：如果我将所有卡片以任何顺序（比如排序或未排序 - 顺序无关紧要）放在链接列表中，这是可能的。我生成一个随机数，将其 mod 设为当前的卡片总数，然后从链表中删除该索引以将卡片存储在我的 shuffledArray 中。

我认为这个解决方案很棒，它具有以下运行时间：O(n) 用于以任何顺序构建链表。O(n) 从链表中删除它。O(1) 用于每次生成一个随机数。

所以或多或少我们有这个算法的 O(n) 下限。

我担心的是空间。目前占用的空间如下： 1) 链表 O(n) 2) shuffledArray O(n)。

再次是 O(n) 的下限。

这可以就地完成吗？我的意思是不使用这个额外的空间。它可以在少于 O(n) 的时间内完成吗？

score 3 · Accepted Answer

3

Fisher-Yates shuffle就地工作，并且恰好生成 n-1 个随机数。

于 2012-06-02T19:04:05.323 回答

score 0 · Accepted Answer

void shuffle(vector<T> v)
{
    int n = v.size();
    for (int i = 0; i < n; i++)
        swap(v[i], v[i+rand(n-i)]);
};

归纳证明：

score -1 · Accepted Answer

如何迭代卡片。在每一步中，您生成一个介于 1 和 52 之间的随机数，并将当前卡与该随机数的卡交换？

你怎么看？

3 回答 3