题目

描述

• 编号为 11 到 nn 的 nn 个人围成一圈。从编号为 11 的人开始报数，报到 mm 的人离开。
  下一个人继续从 11 开始报数。
  n-1轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

方法一

思路

• 创建循环链表，模拟数据淘汰的运行，第n-1次后就能得出最后一个值。

具体步骤

• 创建链表类Node，将所给数据转化成循环链表；

• 模拟运行淘汰数值，找出最后一个值。

• 参考下图示例：
  

• 代码如下

  public class Solution {
    // 链表节点
    class Node{
        int val;
        Node next;
        public Node(int val){
            this.val = val;
        }
    }
    // 初始化链表
    private Node init(int n){
        Node head = new Node(0);
        Node p = head;
        for (int i = 1;i < n;++i){
            p.next = new Node(i);
            p = p.next;
        }
        p.next = head;
        return head;
    }
  
    public int LastRemaining_Solution(int n, int m) {
        // 节点
        if (n == 0 || m == 0){
            return -1;
        }
        if (m == 1){
            return n-1;
        }
        Node head = init(n);
        // 模拟运行
        for(int i = 0;i < n-1;++i){
            for (int j = 0;j < m-2;++j){
                head = head.next;
            }
            Node p = head.next;
            // 淘汰节点
            head.next = head.next.next;
            p.next = null;
            head = head.next;
        }
        return head.val+1;
    }
  }

• 时间复杂度：，双重循环，步数为m，数量为n所以为mn；

• 空间复杂度：循环链表，。

  方法二

  思路

• 约瑟夫环问题，最后存在的值，即为所需要找的数，那么可以从最后一个元素反过来往前推导。在剩下两个元素的时候，删掉另外一个，然后把它往前移动m个位置。所以当需要复原原本的位置时，就需要在当前位置加m，假设当前位置是index_i，那么还剩两个元素的时候的位置就是index_i-1+m,由于是环，所以index+m可能超过长度n了，所以我们要对其进行取模，它的位置是 ，这样就形成了递推公式：

  具体步骤

• 代码如下；

  public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        // 没有元素
        if (m == 0 || n == 0){
            return -1;
        }
        int res = 0;
        for(int i = 2; i <= n; ++i){
            res = (res + m) % i;
        }
        return res+1;
    }
  }

• 时间复杂度：，单层循环；

• 空间复杂度：，常数级空间复杂度。