如何从删除元素的位置开始

Question

我正在做一些面试准备工作，并致力于这个我遇到的代码问题。这些问题说明Given two integers m and n, loop repeatedly through an array of m and remove each nth element. Return the last element left. (If m = 7 and n = 4, then begin with the array 1 2 3 4 5 6 7 and remove, in order, 4 1 6 5 2 7 and return 3.)。从我的作品看，7将是最后的数字，而不是3。

我的思想过程是添加ArrayList或LinkedList中的所有元素，然后使用remove()函数去除传递的位置。我想知道的是，如何从我删除的元素开始，添加那么多索引并删除下一个数字？下面是我的密码。

static int arraryReturn (int [] a, int b, int c) {
    LinkedList<Integer> myList = new LinkedList<>();
    for(int i =0; i< a.length;i++) {
        myList.add(i);
    }


    while(myList.size() > 0) {
        myList.remove(c);

    }



    return -1;
}

Answer 1

适当地，快速解决方案使用一点内存来维护节点图，避免在每一步都遍历n元素。我认为复杂性是O(m)，尽管我没有严格地证明它。

public static void main(String[] args) {
    List<Integer> values = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
    int m = values.size(), n = 4;

    Node[] nodes = initializeGraph(values, m, n);

    Node current = nodes[0];
    for (int i = 0; i < m - 1; i++) {
        Node out = current.out;
        out.remove();
        current = out.right;
    }
    System.out.println(current.value);
}

private static Node[] initializeGraph(List<Integer> values, int m, int n) {
    Node[] nodes = new Node[m];

    for (int i = 0; i < m; i++) nodes[i] = new Node(values.get(i));
    for (int i = 0; i < m; i++) {
        Node current = nodes[i];

        current.right = nodes[(i + 1) % m];
        current.left = nodes[(m + i - 1) % m];
        Node next = nodes[(i + n) % m];

        current.out = next;
        next.addIn(current);
    }

    return nodes;
}

private static class Node {
    private final int value;
    private final Set<Node> in = new HashSet<>();

    private Node out;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    public void addIn(Node node) {
        in.add(node);
    }

    public void remove() {
        left.right = right;
        right.left = left;

        for (Node node : in) {
            node.out = right;
            right.addIn(node);
        }

        out.in.remove(this);
    }
}