从(1 ... n)自然数系列中取出每个第k个元素

Question

例如,我们有系列1,2,3,4,5.我们采用每3个元素=> 3,1,5,2,4(选择的元素不应该保留,我们可以采用系列不为空).圈子双向链表的朴素实现不是表现的好主意.你能给我一个建议,哪些数据结构和算法更适用？

Answer 1

如果你只需要最后一个数字,它就被称为约瑟夫斯问题,并且有众所周知的公式可以O(N)及时计算答案.

我不知道是否可以调整它来运行完整的模拟,所以我将O(N log N)在这里描述一个简单的解决方案:

让我们用隐式密钥保持所有数字.我们需要找到k-th元素并在每一步中删除它(实际上,可能会有一个移位,所以它更像是(cur_shift + k) % cur_size,但它并不重要).一个treap就可以做到.我们只需将其拆分为3个部分[0, k - 1],[k, k]然后[k + 1, cur_size - 1]在与第二部分对应的节点中打印数字,并将第一部分和最后部分合并在一起.它需要O(log N)每步的时间,因此对于给定的约束应该足够好.

Answer 2

构建一个包含数字1到n 的完整二叉树,例如对于n = 15,它将是:

在每个分支中,存储其左侧的节点数; 这将允许我们快速找到第i个节点.(您将看到此树具有非常可预测的结构和值,并且生成它比构建具有随机排序值的相同大小的二叉树更有效.它也是树中的理想候选者.阵列).

然后,要找到第i个数字,从根节点开始,并且在每个节点,如果i大于左边的节点数,则找到第i个数字,否则向左移动(如果i不大于左边或右边的节点数(如果i比左边的节点数大1).

无论何时向左移动,都会减少此节点左侧的节点数(因为我们将删除一个节点).

无论何时向右移动,请通过节点左侧的节点数减1来增加1(如果节点中的值已被删除,则减去0).

找到第i个节点后,读取其值(添加到删除顺序列表),然后将其值设置为0.此后,如果我们要查找的第i个节点的值已被删除,我们会向右走,然后走最左边的节点.

我们从值i = k开始,然后每当我们删除第i个节点中的数字时,我们将减少节点的总数并设置i = (i + k - 1) % total(或者如果它为零:)i = total.

这给出了log ₂ N的查找时间和N×LogN的总复杂度.

示例演练:n = 15(如上图所示)和k = 6,第一步是6,12,3,10,2.此时的情况是:

我们刚刚删除了第二个号码i = 2 + 6 - 1 = 7.我们从根节点开始,它在它的左边有4个节点并且仍然有它的值,所以我们右边从我们正在寻找的7中减去5并得到2.我们到达节点12(已经到了擦除)并找到它左边有2个节点,所以我们减少它左边的节点数然后再向左移动.我们来到节点10(已被删除)并发现它左边有1个节点,1 = 2 - 1所以这是我们正在寻找的节点; 然而,由于它的值已被删除,我们向右移动并从我们正在寻找的2中减去1并得到1.我们到达节点11,其左边有0个节点(因为它是叶子),并且0 = 1 - 1,所以这是我们正在寻找的节点.

然后,我们将节点总数从10减少到9,并将i从7更新为(7 + 6 - 1) % 9 = 3,然后继续查找第三个节点(现在是值为5的节点).

这是JavaScript中的一个简单实现.它可以在不到一秒的时间内解决100,000个数字系列,并且可以通过使用树形数组结构使其更快,更节省空间.

(与上面的解释不同,数字的索引是从零开始的,以简化代码;因此索引0是树中的第一个数字,我们查找具有多个左连接子节点的节点,该节点等于目标指数.)

function Tree(size) {                      // CONSTRUCTOR
    var height = Math.floor(Math.log(size) / Math.log(2));
    this.root = addNode(height, 1 << height, size);
    this.size = size;
    function addNode(height, value, max) { // RECURSIVE TREE-BUILDER
        var node = {value: value > max ? 0 : value, lower: (1 << height) - 1};
        if (height--) {
            node.left = addNode(height, value - (1 << height), max);
            if (value < max) {             // DON'T ADD UNNECESSARY RIGHT NODES
                node.right = addNode(height, value + (1 << height), max);
            }
        }
        return node;
    }
}
Tree.prototype.cut = function(step) {      // SEE ANSWER FOR DETAILS
    var sequence = [], index = (step - 1) % this.size;
    while (this.size) {
        var node = this.root, target = index;
        while (node.lower != target || node.value == 0) {
            if (target < node.lower) {
                --node.lower;
                node = node.left;
            } else {
                target -= node.lower + (node.value ? 1 : 0);
                node = node.right;
            }
        }
        sequence.push(node.value);
        node.value = 0;
        index = (index + step - 1) % --this.size;
    }
    return sequence;
}
var tree = new Tree(15);
var sequence = tree.cut(6);
document.write("15/6&rarr;" + sequence + "<BR>");

tree = new Tree(100000);
sequence = tree.cut(123456);
document.write("100000/123456&rarr;" + sequence);

注意:

如果你看n = 10的树,你会看到根右边的节点有一个不完整的树,左边有2个节点,但是上面代码示例中实现的算法给出了一个错误的左边 - 节点数为3而不是2:

但是,左侧不完整树的节点本身从不持有值,并且从不拥有​​右侧的节点.因此,无论如何你总是离开那里,而且他们的左侧节点数太高这一事实并不重要.