面试题45. 圆圈中最后剩下的数字

本文主要是介绍面试题45. 圆圈中最后剩下的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,求最后一个小朋友的编号
(注：小朋友的编号是从0到n-1)

这道题是著名的约瑟夫环问题，举个例子，现在有6个人，编号从0到5，每次删除第3个人。
第一次删除2，还剩 0,1,3,4,5，然后从3开始继续报数和删除的过程
第二次删除5，还剩 0,1,3,4, 然后从0开始继续
第三次删除3，还剩 0,1,4, 然后从4开始继续
第四次删除1，还剩 0,4, 然后从4开始继续
第五次删除4，还剩 0，结束

思路1：
用boolean数组进行模拟，数组长度为n。每一个数组元素被初始化为false，arr[i] = false 表示编号为 i 的人没有被排除；反之arr[i] = true表示编号为 i 的人被排除。

分析这种方法可以发现，每排除一个人需要m步运算，n个人就需要O(mn)，空间复杂度为O(n).

public class Solution {public int LastRemaining_Solution(int n, int m) {// 不合法输入的判断if(n == 0 || m < 1) {return -1;}// 如果m大于nint temp = m;boolean mOvern = false;if(m > n) {m = m % n; // m要被重新赋值为 m % nmOvern = true;}// 使用boolean数组进行模拟，初始化为false// 表示大家都没有被排除，被排除用true表示boolean[] arr = new boolean[n];int leftCount = n; // 剩余的人数int count = 0; // 计数int index = 0; // 当前的编号while(leftCount > 1) {        	        	      count++;             	if(count == m) { // 如果数到第m个人count = 0;leftCount--;arr[index] = true; // 这个人被排除// 排除一个人以后，要重新计算m的值if(mOvern) {m = temp % leftCount;m = m == 0 ? leftCount : m;}}index = (index + 1) % n;while(arr[index]) { // 寻找下一个没有被排除的人index = (index + 1) % n;}            }return index;}
}

思路2：

用链表模拟，比思路1的数组模拟要快

public int LastRemaining_Solution(int n, int m) {if (n == 0 || m == 0) return -1;LinkedList<Integer> list = new LinkedList<>();for (int i = 0; i < n; i++) {list.add(i);}int count = 1, i = 0;while (list.size() > 1) {if (i == list.size()) {i = 0;}if (count % m == 0) {list.remove(i);count = 1;} else {i++;count++;}}return list.get(0);}

思路3：

创新的解法，采用数学公式推导找到规律，推导过程如下：

Step1.
首先定义一个关于 m 和 n 的函数：f(n, m)，表示在n个数字 0,1,2…,n-1 中每次删除第m个数字，最后剩下的那个数字。
注意：f(n, m)表示的是，在经过了多次删除后，最后剩下的那个数字，也就是说f(n,m)本质上是个数。

Step2.
n个数中，第一个被删除的数是(m - 1) % n，把它记为k，此时数组中还剩下0,1,2… k-1, k+1,…n-1 这几个数字。接下来从k+1开始计数，相当于在剩下的序列中，k+1排在最前面，从而形成k+1,… n-1,… 0,1,2…k-1。本题中，第一个被删除的是数字2，因此数组还剩下 0,1,3,4,5，相当于3,4,5,0,1。由于这个序列是不连续的，在2那个地方断开了，所以不能写为f(n-1, m)。在此记为g(n-1, m)。
最初序列最后剩下的数字，一定是删除一个数字后剩下的数字，因此f(n, m) = g(n-1, m)

Step3.
将[3,4,5,0,1]重新映射为[0,1,2,3,4]，映射的公式是：p(x) = (x - k - 1) % n。其中k = 2，n = 6。
3 ----> 0
4 ----> 1
5 ----> 2
0 ----> 3
1 ----> 4
映射以后的序列是0,1,2,3,4，是一个连续的序列，因此可以用f(n-1, m)来表示。
此时的f(n-1, m)是不等于g(n-1, m)，因为二者对应的序列不同，存在一个映射关系。
该映射的逆映射是 p’(x) = (x + k + 1) % n
因此g(n-1, m) = p’[f(n-1, m)] = [f(n-1, m) + k + 1] % n
即：f(n, m) = [f(n-1, m) + k + 1] % n
带入k = (m - 1) % n, 得到f(n, m) = [f(n-1, m) +m] % n (n > 1)

Step4.
当n = 1时，只有一个人，此时剩余的数字为0

综上，约瑟夫环的公式是：
f(n, m) = 0 (n = 1)
f(n, m) = [f(n-1, m) +m] % n (n > 1)

public class Solution {public int LastRemaining_Solution(int n, int m) {// 不合法输入的判断if(n == 0 || m < 1) {return -1;}        int last = 0;for(int i = 2; i <= n; i++) {last = (last + m) % i;}return last;}}