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

Question

我正在做一些面试准备，并正在研究我遇到的这个 leetcode 问题。问题说明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。我的思考过程是将所有元素添加到一个ArrayListor 中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);

    }

}