题目

0,1,...,n-1n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

其实这就是著名的约瑟夫环问题,下面是这个问题产生的背景,一个有趣的故事:

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

foo

思路

解法1:用链表模拟环

  • 用链表模拟一个环

  • 模拟游戏场景

  • 记录头节点的前一个节点current,以保证我们找到的要删除的节点是current.next

  • 每次循环m次找到目标节点删除,直到链表只剩下一个节点

  • 时间复杂度O(m*n) 空间复杂度O(n)

解法2:用数组模拟

  • 每次计算下标,需要考虑末尾条件

解法3:数学推导

  • f(n) = (f(n-1)+m)%nf(n,m) = (f(n-1,m)+m)%n
  • 使用递归求解 边界条件为 n=1

时间复杂度 1>2>3

易理解程度 1>2>3

代码

    // 解法1
    function LastRemaining_Solution(n, m) {
      if (n < 1 || m < 1) {
        return -1;
      }
      const head = { val: 0 }
      let current = head;
      for (let i = 1; i < n; i++) {
        current.next = { val: i }
        current = current.next;
      }
      current.next = head;

      while (current.next != current) {
        for (let i = 0; i < m - 1; i++) {
          current = current.next;
        }
        current.next = current.next.next;
      }
      return current.val;
    }
    // 解法2
    function LastRemaining_Solution(n, m) {
      if (n < 1 || m < 1) {
        return -1;
      }
      const array = [];
      let index = 0;
      for (let i = 0; i < n; i++) {
        array[i] = i;
      }
      while (array.length > 1) {
        index = (index + m) % array.length - 1;
        if (index >= 0) {
          array.splice(index, 1);
        } else {
          array.splice(array.length - 1, 1);
          index = 0;
        }
      }
      return array[0];
    }
    // 解法3
    function LastRemaining_Solution(n, m) {
      if (n < 1 || m < 1) {
        return -1;
      } else {
        return joseoh(n, m);
      }

    }

    function joseoh(n, m) {
      if (n === 1) {
        return 0;
      }
      return (joseoh(n - 1, m) + m) % n;
    }
Last Updated: 8/4/2019, 9:40:51 PM