从（1 .. n）自然数序列中获取第k个元素 [英] Take every k-th element from the (1 .. n) natural numbers series

问题描述

例如，我们有序列1、2、3、4、5。我们每3个元素取=>
3、1、5、2、4（选择的元素不应保留，我们可以取而系列不为空）。圆双链表的幼稚实现不是好主意的性能原因。您能给我建议哪种数据结构和算法更适用？

解决方案

构建

在每个分支中，存储左侧的节点数；这将使我们能够快速找到第i个节点。 （您会看到这棵树具有非常可预测的结构和值，与生成具有随机顺序值的相同大小的二叉树相比，生成它的效率要高得多。它也是树入的理想选择-an-array。）

然后，找到第i个数字，从根节点开始，在每个节点上（如果i为1）大于左侧的节点数，您已经找到了第i个数字，否则向左（如果i不大于左侧的节点数）或向右（如果i大于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是树中的第一个数字，然后寻找具有等于目标索引的左连接子项的节点。）

 函数树（大小）{//构造函数var height = Math.floor（Math.log（size）/ Math.log（2））; this.root = addNode（height，1<< height，size）; this.size =大小； function addNode（height，value，max）{//递归树构建器var node = {value：value>最大？ 0：值，下限：（1 ＜＜高度）-1}； if（height--）{node.left = addNode（height，value-（1<< height），max）; if（value< max）{//不要添加不必要的权限节点node.right = addNode（height，value +（1<< lt; height），max）;返回节点； }} Tree.prototype.cut = function（step）{//查看详细信息，请参见var sequence = []，index =（步骤-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 =（索引+步骤-1）％--this.size; }返回序列；} var tree = new Tree（15）; var sequence = tree.cut（6）; document.write（ 15/6& rarr; + sequence +< BR>）; tree = new Tree（100000）;序列= tree.cut（123456）; document.write（ 100000/123456& rarr; +序列）;  

---

注意：

如果查看n = 10的树，您会看到根右边的节点有一个不完整的树，左边有2个节点，但是上面代码示例中实现的算法为它提供了一个错误的左节点计数3而不是2：

但是，左侧有不完整树的节点自己永远不会拥有值，右侧也永远不会具有节点。因此，无论如何，您总是要离开那里，而其左节点数太高这一事实也就无关紧要。

For example, we have series 1, 2, 3, 4, 5. We take every 3 element => 3, 1, 5, 2, 4 (chosen element shouldn't remain, we can take while series is not empty). Naive implementation by circle doubly linked list is not good idea cause of performance. Can you give me an advice which data structures and algorithms are more applicable?

解决方案

Build a complete binary tree containing the numbers 1 to n, e.g. for n=15 that would be:

In each branch, store the number of nodes to the left of it; this will allow us to quickly find the i-th node. (You'll see that this tree has a very predictable structure and values, and generating it is much more efficient than building a same-sized binary tree with randomly-ordered values. It's also an ideal candidate for a tree-in-an-array.)

Then, to find the i-th number, start at the root node, and at every node, if i is one greater than the number of nodes to the left, you've found the i-th number, else go left (if i is not greater than the number of nodes to the left) or right (if i is more than 1 greater than the number of nodes to the left).

Whenever you go left, decrement the count of nodes to the left of this node (because we'll be removing one).

Whenever you go right, decrease the number you're looking for by the number of nodes to the left of the node, plus 1 (or plus 0 if the value in the node has been erased).

When you've found the i-th node, read its value (to add to the removal order list) and then set its value to 0. Thereafter, if the i-th node we're looking for has had its value erased, we'll go right and then take the leftmost node.

We start with a value i = k, and then every time we've erased the number in the i-th node, we'll decrement the total number of nodes and set i = (i + k - 1) % total (or if that is zero: i = total).

This gives a log₂N lookup time and a total complexity of N×LogN.

---

Example walk-through: with n=15 (as in the image above) and k=6, the first steps are 6, 12, 3, 10, 2. At that point the situation is:

We've just removed the second number, and now i = 2 + 6 - 1 = 7. We start at the root node, which has 4 nodes to the left of it and still has its value, so we go right and subtract 5 from the 7 we're looking for and get 2. We arrive at node 12 (which has been erased) and find there are 2 nodes to the left of it, so we decrement the number of nodes to the left of it and then go left. We come to node 10 (which has been erased) and find that it has 1 node to the left of it, and 1 = 2 - 1 so this is the node we're looking for; however, since its value has been erased, we go right and subtract 1 from the 2 we're looking for and get 1. We arrive at node 11, which has 0 nodes to the left of it (because it's a leaf), and 0 = 1 - 1, so this is the node we're looking for.

We then decrement the total number of nodes from 10 to 9, and update i from 7 to (7 + 6 - 1) % 9 = 3 and go on to find the third node (which is now the one with value 5).

---

Here's a simple implementation in JavaScript. It solves series of 100,000 numbers in less than a second, and it could probably be made faster and more space-efficient by using a tree-in-an-array structure.

(Unlike in the explanation above, the indexes of the numbers are zero-based, to simplify the code; so index 0 is the first number in the tree, and we look for the node with a number of left-connected children that equals the target index.)

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);

---

NOTE:

If you look at the tree for n=10, you'll see that the node to the right of the root has an incomplete tree with 2 nodes to its left, but the algorithm as implemented in the code example above gives it an incorrect left-node count of 3 instead of 2:

However, nodes with an incomplete tree to their left never hold a value themselves, and never have nodes to their right. So you always go left there anyway, and the fact that their left-node count is too high is of no consequence.

这篇关于从（1 .. n）自然数序列中获取第k个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！