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

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) {&nbsp; &nbsp; List<Integer> values = Arrays.asList(1, 2, 3, 4, 5, 6, 7);&nbsp; &nbsp; int m = values.size(), n = 4;&nbsp; &nbsp; Node[] nodes = initializeGraph(values, m, n);&nbsp; &nbsp; Node current = nodes[0];&nbsp; &nbsp; for (int i = 0; i < m - 1; i++) {&nbsp; &nbsp; &nbsp; &nbsp; Node out = current.out;&nbsp; &nbsp; &nbsp; &nbsp; out.remove();&nbsp; &nbsp; &nbsp; &nbsp; current = out.right;&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(current.value);}private static Node[] initializeGraph(List<Integer> values, int m, int n) {&nbsp; &nbsp; Node[] nodes = new Node[m];&nbsp; &nbsp; for (int i = 0; i < m; i++) nodes[i] = new Node(values.get(i));&nbsp; &nbsp; for (int i = 0; i < m; i++) {&nbsp; &nbsp; &nbsp; &nbsp; Node current = nodes[i];&nbsp; &nbsp; &nbsp; &nbsp; current.right = nodes[(i + 1) % m];&nbsp; &nbsp; &nbsp; &nbsp; current.left = nodes[(m + i - 1) % m];&nbsp; &nbsp; &nbsp; &nbsp; Node next = nodes[(i + n) % m];&nbsp; &nbsp; &nbsp; &nbsp; current.out = next;&nbsp; &nbsp; &nbsp; &nbsp; next.addIn(current);&nbsp; &nbsp; }&nbsp; &nbsp; return nodes;}private static class Node {&nbsp; &nbsp; private final int value;&nbsp; &nbsp; private final Set<Node> in = new HashSet<>();&nbsp; &nbsp; private Node out;&nbsp; &nbsp; private Node left;&nbsp; &nbsp; private Node right;&nbsp; &nbsp; public Node(int value) {&nbsp; &nbsp; &nbsp; &nbsp; this.value = value;&nbsp; &nbsp; }&nbsp; &nbsp; public void addIn(Node node) {&nbsp; &nbsp; &nbsp; &nbsp; in.add(node);&nbsp; &nbsp; }&nbsp; &nbsp; public void remove() {&nbsp; &nbsp; &nbsp; &nbsp; left.right = right;&nbsp; &nbsp; &nbsp; &nbsp; right.left = left;&nbsp; &nbsp; &nbsp; &nbsp; for (Node node : in) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.out = right;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right.addIn(node);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; out.in.remove(this);&nbsp; &nbsp; }}