题目
题目:有n个人,围成一个环，编号为 0、1、2、3、、、n-1，从第一个人开始循环报数(从1开始)，假设数到m的那个人出列，然后从下一个人继续数数，数到m出列，以此循环，最后那个人为胜利者，求胜利者的编号。
这其实就是有名的约瑟夫问题。
输入示例
- n=4, m=3 result=0
- n=50, m=20 result=33
- n=100, m=37 result=44
思路
解法一--模拟法
可以使用数组或者链表来模拟这n个人，每次删除第m个人，直到只剩下一个人为止。
使用数组删除元素的复杂度较高，链表是最优选择，C++ stl中的链表用的不太熟练，所以自己写一个。为了删除方便，选择双向链表，单向链表删除的时候还需要两个指针，很麻烦。
class Solution {
public:
struct Node{
int val;
Node* next;
Node* parent;
}; // 链表节点
int LastRemaining_Solution(int n, int m)
{
if(m == 0 || n == 0)
return -1; // 无效情况返回-1
// 为所有节点分配空间
vector<Node> node(n);
//头节点单独赋值
node[0].val = 0;
//构造链表
for(int i=1;i<n;i++){
node[i].val = i; //编号
node[i].next = NULL;
node[i-1].next = &node[i];
node[i].parent = &node[i-1];
}
node[n-1].next = &node[0];
node[0].parent = &node[n-1];
//模拟
int num = n; //还剩下的人数
Node *head = &node[0]; //头节点
//在只剩下一个人的时候停止模拟
while(num > 1){
// 找到第m个
int count = 0;
while(count < m-1){
head = head->next;
count ++;
}
//找到了第m个 开始删除
head->parent->next = head->next;
head->next->parent = head->parent;
head = head->next;
num --; // 剩余人数减1
}
return head->val;
}
};
这种算法时间复杂度为O(mn)，空间复杂度为O(n)。
解法二--数学推导
感觉应该存在某种规律，但我等数学渣渣并不能够推导出来。
看完书上的解答，表示有点绕，现在用自己的话解释一遍：
f(n,m):表示 每次在n个数字0，1,...,n-1中删除第m个数字最后剩下的数字（也就是要求的结果）。（注意，要求数字标号需要是连续的，所以后面删除一个元素后标号不连续了，需要重新标号）。
在这n个数字中，第一个被删除的数字是 (m-1)%n (取余的原因是m可能比n大)，记作k，则k=(m-1)%n。删除后的序列为 0,1,...,k-1,k+1,...,n-1。由于下一次删除是从k+1开始计数的，所以相当于从标号为k+1,k+2,...,n-1,0,1,2,...,k-1的序列中继续删除第m个数字，最终剩下的数字就是结果。
剩下的n-1个数字如果重新按顺序标号得到序列0,1,...,n-2，则每次删除第m个数，最后剩下的数字就是f(n-1,m)。由于重新标号了，所以并不是f(n,m)=f(n-1,m)! 那么f(n-1,m)对应的数字在修改标号之前是什么数呢？
事实上，原先的不连续的序列A(k+1,k+2,...,n-1,0,1,2,...,k-1)变成了序列B(0,1,...,n-2)，而我们主要是想知道如何从序列B中的某个数找到序列A中对应的关系，先建立个映射表格：
| B序列 | 序列A |
|---|---|
| 0 | k+1 |
| 1 | k+2 |
| n-k-2 | n-1 |
| n-k-1 | 0 |
| n-k | 1 |
| n-2 | k-1 |
| f(n-1,m) | (f(n-1,m)+k+1)%n |
根据表格，可以很直观的看出，在B序列中数字x，对应于A序列中的(x+k+1)%n（注意：必须取余数，因为B序列中为n-k,而n-k+k+1为n+1,必须取余数才能得到1）。所以在B序列中标号为f(n-1,m)，对于在A序列中就为(f(n-1,m)+k+1)%n。
还记得k吗，k就是在第一次删除的时候删掉的数(与n有关的变量)，k=(m-1)%n。
将其带入上面的式子，就得到:
(f(n-1,m)+k+1)%n = (f(n-1,m)+(m-1)+1)%n = (f(n-1,m)+m)%n
因此，我们就得到了这个递归公式，而当n=1的时候，也就是序列中只有标号为0的数字，显然最后剩下的数字就是0，所以整个公式就是：
递归公式.png
根据这个公式，写代码就很简单了。
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(m == 0 || n == 0)
return -1; // 无效情况返回-1
int last = 0;
for(int i=2;i<=n;i++)
last = (last+m) % i;
return last;
}
};
这种算法的时间复杂度是O(n)，空间复杂度是O(1)，远远优于第一种算法，但是推导复杂，数学渣渣表示如果没见过这个题，绝对推导不出来。。。
总结
使用链表模拟的常规解法必须掌握，数学推导，那就看状态吧。。
网友评论