【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）
62 圆圈中最后剩下的数字（约瑟夫环问题）
题目描述
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
方法一：用数组模拟过程（也可以用链表模拟）
/*
约瑟夫环问题
方法一：用数组模拟过程，删除之后剩下的元素即为最后结果(可用状态数组)
81ms,有点慢
O(nlogm(n)), O(n)
*/
class Solution
{
public:
int LastRemaining_Solution(int n, int m)
{
vector<int> state(n, 1); //定义一个数组存储各元素的状态
int count_del = 0; //对删除的数字计数
int count = 0; //用于数哪个数被删除
int i = 0; //索引
for(; count_del < n; i++)
{
if(i == n) i = 0;
if(state[i] == 1) count++;
if(count == m) //第m个数时进行“删除”
{
count = 0;
count_del++;
state[i] = 0; //更改状态，0表示已经被删除
}
} //退出循环时，最后一个元素状态被置0,i++会执行一次，故应返回i-1
return i-1;
}
};
方法二：找递推公式
现在先将n个人按照编号进行排序：
0 1 2 3 … n-1
那么第一次被淘汰的人编号一定是K-1(假设K < n，若K > n则为(K-1) mod n)。将被选中的人标记为”#”：
0 1 2 3 … K-2 # K K+1 K+2 … n-1
第二轮报数时，起点为K这个候选人。并且只剩下n-1个选手。假如此时把k看作0’，k+1看作1’…
则对应有：
此时在0’,1’,…,n-2’上再进行一次K报数的选择。假设f[n-1]的值已经求得，因此我们可以直接求得当选者的编号s’。
但是，该编号s’是在n-1个候选人报数时的编号，并不等于n个人时的编号 ，所以我们还需要将s’转换为对应的s。
通过观察，s和s’编号相对偏移了K，又因为是在环中，因此得到s = (s'+K) mod n。
即f[n] = (f[n-1] + k) mod n。
/*
方法二：推出递推公式（动态规划）
i = 1, res =0
i = 2, res = (0+3)%2 = 1
i = 3, res = (1+3)%3 = 1
i = 4, res = (1+3)%4 = 0
...
O(n),O(1)
*/
class Solution
{
public:
int LastRemaining_Solution(int n, int k)
{
if(n < 1 || k < 1) return -1; //返回-1表示非法输入
int last = 0;
for(int i = 2; i<=n; i++)
last = (last + k) % i; //i个人时删除数的索引等于i-1个人时删除数的索引+k(再对i取余)
return last;
}
};