问大k上的Josephus序列
EN

Stack Overflow用户

提问于 2021-01-15 18:06:48

回答 2查看 127关注 0票数 2

在Josephus问题中，我们有n个人，从1到n。每轮你跳过k个人，然后杀死下一个人。通常你会把最后一个幸存者放在我感兴趣的受害者序列上。我尝试使用基于在线建议的循环链表来实现这一点。当输入很大的时候，比如n=123456；k=1000000000，我的算法仍然不够快。我的时间目标是不到一秒。我认为时间复杂度是O(nk)，因为所有的链表操作都是O(1)，并且对于每个人，我必须打印它们的值，并可能移动k个步骤。我是否应该找到一些不同的策略，是不是我错过了一些明显的优化技术？

#include <vector>
using namespace std;
 
struct Node {
    int value;
    struct Node* next;
};
 
Node* insertToEmpty(struct Node* last, int x) {
    Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->value = x;
    last = temp;
    last->next = last;
    return last;
}
 
Node* insert(struct Node* last, int x) {
    if (last == NULL) {
        return insertToEmpty(last, x);
    }
    Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->value = x;
    temp->next = last->next;
    last->next = temp;
    last = temp;
    return last;
}
 
Node* delete2(struct Node* prev, struct Node* current) {
    prev->next = current->next;
    return current->next;
}
 
int main() {
    int n;
    int k;
    cin >> n;
    cin >> k;
    if (n == 1) {
        cout << 1;
    }
    else {
        struct Node* curr;
        struct Node* prev;
        struct Node* last = NULL;
        for (int i = 1; i <= n; i++) {
            last = insert(last, i);
        }
        curr = last->next;
        prev = curr;
        for (int i = 1; i <= k%n; i++) {
            prev = curr;
            curr = curr->next;
        }
        do {
            cout << curr->value << " ";
            curr = delete2(prev, curr);
            n--;
            for (int j = 0; j < k%n; j++) {
                prev = curr;
                curr = curr->next;
            }
        } while (n > 1);
        cout << curr->value << endl;
 
    }
 
}

algorithm

linked-list

computer-science

josephus

c++

电商安全场景方案

帮助电商行业客户一站式解决Web安全、黑产羊毛党对抗、高危漏洞、BOT工具、恶意入侵门户服务器等安全问题

回答 2

Stack Overflow用户

发布于 2021-01-15 20:37:12

您说得对，使用简单的链表是O(nk)，如果您想要加快速度，就必须使用更好的数据结构。我建议您使用skip list的变体来解决此问题。

跳过列表是一种二维结构。所有的值都在最底层。每一级以上只有一些值。它跳过了其他的。如果要移动固定数量的步数，您可以向前和向上移动，跳过元素，直到可以向前和向下移动到正确的位置。所有的运算都是对数的。在您的例子中，这将使算法成为O(n (log(n) + log(k))

在这种结构中，一个节点将如下所示：

struct Node {
    int value;
    int count;
    struct Node* parent;
    struct Node* next;
    struct Node* first_child;
};

当您构建它时，您的底层将如下所示：

1 <-> 2 <-> 3 <-> ... <-> n

其中first_child为null，parent为指向下一层的指针，count为1。

您的第二层将如下所示：

1 <-> 3 <-> 5 <-> ... <-> (n-1 or n as appropriate)

first_child指向下一层中的相同值，parent指向上一层，count为2。

您的第三层将如下所示：

1 <-> 5 <-> 9 <-> 13 <-> ... <-> (something from n-3 to n)

first_child指向下一层中的相同值，parent指向上一层，count为4。

依此类推，直到最顶层只包含1，并且下一个值不在数组的末尾。将会有O(log(n))级别。

好了，这就是设置。我们如何删除某些东西？我将用一种我不知道的语言编写未经测试的代码，请原谅语法错误：

void remove (Node* node) {
    if (0 == --node->count) {
        /* Actually delete */
        if (node->prev != null) {
            node->prev->next = node->next;
        }
        if (node->next != null) {
            node->next.prev = node->prev;
        }
        if (node->parent != null && node = node->parent.first_child) {
            node->parent->first_child = node->next;
            node->parent->value = node->next->value;
        }
    }
    if (node->parent != null) {
        remove(node->parent);
    }
    if (0 == node->count) {
        free(node);
    }
}

此操作需要O(log(n))时间，因为这就是级别的数量。

接下来，我们将需要一个小的辅助函数来查找块中的最后一个节点。这意味着我们想要向下向右移动，直到我们到达那个节点。

Node* last_in_block (Node* node) {
    if (node->next == null) {
        /* Slide down the end. */
        while (node->first_child != null) {
            node = node->first_child;
        }
    }
    else {
        while (node->first_child != null) {
            Node* child = node->first_child;
            while (child->next->parent == node) {
                child = child->next;
            }
            node = child;
        }
    }
    return node;
}

现在，向前推进一些步骤如何？这有点棘手。

首先，让我们达成共识，在一个特定的地点意味着“我刚刚访问过这里，然后继续前进。”因此，我们可以递归地将move定义为“查找要跳过的节点，然后从块中减去它的计数”。但也有一些边缘情况。同样是未经测试的代码，但下面应该给出我所指的大体概念。

Node* move (Node* node, int steps) {
    if (node->next == null) {
        /* We are at the end, go to the top */
        while (node->parent != null) {
            node = node->parent;
        }

        /* Go around the loop as many times as needed. */
        steps = steps % node->count;

        /* Travel down to the right level to continue our journey */
        while (steps < node->count) {
            node = node->first_child;
        }

        /* And step over this node */
        steps -= node->count;
    }

    if (steps <= 0) {
        /* EXIT HERE IF JOURNEY IS ENDED */
        return last_in_block(node);
    }

    /* Right now the following are true.

       1. We are not at the end.
       2. We are also not at the top level (because the node there is at the end).
       3. node->next is also not at the top level (because it is at our level).
       4. 0 < steps, so traveling down we will eventually find a doable step.
    */

    if (steps <= node->next->count) {
        /* travel forward, then down to the right level. */
        node = node->next;
        while (steps < node->count) {
            node = node->first_child;
        }
    }
    else if (node->parent != node->next->parent && node->next->parent->count < steps) {
        /* travel forward and then up */
        node = node->next;
        while (node->parent != null && node->parent->count < steps) {
            node = node->parent;
        }
    }
    else {
        /* just travel forward */
        node = node->next;
    }
    /* And now we step over the block represented by this node. */
    steps -= node->count;
    return move(node, steps);
}

现在有了这个数据结构，你就可以知道如何前进，移除你所站的斑点，再次前进，等等。

票数 1

Stack Overflow用户

发布于 2021-01-16 16:33:34

我们可以通过使用treap with a size decoration来独立于k。O(n log n)。

示例输入，输出：

stdin:   10 5
stdout:  4 9 5 1 8 7 0 3 6

C++改编自Kimiyuki Onaka的代码：

#include <iostream>
#include <tuple>
#include <random>
#include <memory>

using namespace std;

template <typename T>
struct treap {
    typedef T value_type;
    typedef double key_type;
    value_type v;
    key_type k;
    shared_ptr<treap> l, r;
    size_t m_size;
    treap(value_type v)
            : v(v)
            , k(generate())
            , l()
            , r()
            , m_size(1) {
    }
    static shared_ptr<treap> update(shared_ptr<treap> const & t) {
        if (t) {
            t->m_size = 1 + size(t->l) + size(t->r);
        }
        return t;
    }
    static key_type generate() {
        static random_device device;
        static default_random_engine engine(device());
        static uniform_real_distribution<double> dist;
        return dist(engine);
    }
    static size_t size(shared_ptr<treap> const & t) {
        return t ? t->m_size : 0;
    }
    static shared_ptr<treap> merge(shared_ptr<treap> const & a, shared_ptr<treap> const & b) { // destructive
        if (not a) return b;
        if (not b) return a;
        if (a->k > b->k) {
            a->r = merge(a->r, b);
            return update(a);
        } else {
            b->l = merge(a, b->l);
            return update(b);
        }
    }
    static pair<shared_ptr<treap>, shared_ptr<treap> > split(shared_ptr<treap> const & t, size_t i) { // [0, i) [i, n), destructive
        if (not t) return { shared_ptr<treap>(), shared_ptr<treap>() };
        if (i <= size(t->l)) {
            shared_ptr<treap> u; tie(u, t->l) = split(t->l, i);
            return { u, update(t) };
        } else {
            shared_ptr<treap> u; tie(t->r, u) = split(t->r, i - size(t->l) - 1);
            return { update(t), u };
        }
    }
    static shared_ptr<treap> insert(shared_ptr<treap> const & t, size_t i, value_type v) { // destructive
        shared_ptr<treap> l, r; tie(l, r) = split(t, i);
        shared_ptr<treap> u = make_shared<treap>(v);
        return merge(merge(l, u), r);
    }
    static pair<shared_ptr<treap>,shared_ptr<treap> > erase(shared_ptr<treap> const & t, size_t i) { // (t \ t_i, t_t), destructive
        shared_ptr<treap> l, u, r;
        tie(l, r) = split(t, i+1);
        tie(l, u) = split(l, i);
        return { merge(l, r), u };
    }
};

typedef treap<int> T;
int main() {
    int n; cin >> n;
    int k; cin >> k;
    shared_ptr<T> t;
    for (int i=0; i<n; i++)
        t = T::insert(t, i, i);
    
    int size = n;
    int position = 0;
    for (int i=0; i<n-1; i++){
        position = (position - 1 + k) % size;
        size = size - 1;
        shared_ptr<T> u;
        tie(t, u) = T::erase(t, position);
        cout << u->v << " ";
    }
    cout << endl;
    return 0;
}