圆圈中最后剩下的数

题目描述

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

解法一：

这其实是一个约瑟夫环问题，由题意知可以通过环形链表来解决这个问题。

public class Solution {
    public static int LastRemaining_Solution(int n, int m) {
        if(n <= 0 || m <= 0)
            return -1;
        ListNode start = new ListNode(0);
        ListNode index = start;
        for(int i = 1; i < n; i++) {
            index.next = new ListNode(i);
            index = index.next;
        }
        index.next = start;
        ListNode before = index;
        index = start;
        while(index.next != index) {
            for(int i = 0; i < m - 1; i++) {
                index = index.next;
                before = before.next;
            }
            before.next = index.next;
            index = index.next;
        }
        return index.val;
    }
}
class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }

解法二：

我们定义在n个数字0，1，2，3，……，n-2，n-1（记为序列F）中每次循环删除第m个数字最后剩下的数字为f（n，m），

上面的序列第一个删除的数字为（m-1）%n，记为k，则删除第一个数字后序列变为0，1，2，3，……，k-1，k+1，……，n-2，n-1，之后从k+1开始重新计数，即

k+1，k+2，……，n-2，n-1，0，1，2，3，……，k-1（记为序列G）

序列不是像f（n，m）一样从小到大的，但我们可以用g（n-1，m）来表示上面的序列每次循环删除第m个数字最后剩下的数字

很显然，f（n，m）= g（n-1，m）

其实通过观察我们可以发现序列G可以转换成序列F的形式

[table id=6 /]

第2到7行很容易理解，F = G - k - 1即可

但是到了第8行，若继续F = G - k - 1得到-k-1，与期望的n-k-1不等，但是我们发现只要将映射关系调整为F = （G - k - 1）% n即可满足全部数字。

所以我们得到映射关系 ：F = （G - k - 1）% n

序列G可以通过（“序列G” - k - 1） % n的方法转变为 0，1，2，3，……，n-2，n-1，序列都一样了则最后的结果肯定也一样，即[g(n-1, m)- k - 1] % n = f(n-1, m)

很简单可以推得 g(n-1, m) = [f(n-1, m) + k + 1] % n

由于f（n，m）= g（n-1，m），

所以**f(n, m)= **[f(n-1, m) + k + 1] % n，**** 将k = (m - 1) % n代入得

f(n, m) = [f(n - 1, m) + m] % n

这是一个递推公式，很明显

image

根据这个公式采用循环或递归可以很容易得到答案。采用循环的时间复杂度为O（n），空间复杂度为O（1）