数组模拟双向链表解决
class Solution {
public:
static const int N=1e5+10;
int e[N],l[N],r[N],idx;
void init(){
r[0]=1,l[1]=0,idx=2;
}
void add(int x){
e[idx]=x;
l[idx]=l[1],r[idx]=1;
r[l[1]]=idx,l[1]=idx++;
}
int rem(int k){
r[l[k]]=r[k],l[r[k]]=l[k];
return r[k];
}
int lastRemaining(int n, int m){
init();
for(int i=0;i<n;i++) add(i);
int s=n-1,pos=r[0];
while(s--){
int k=m-1;
while(k--){
pos=r[pos];
if(pos==1) pos=r[0];
}
pos=rem(pos);
if(pos==1) pos=r[0];
}
return e[r[0]];
}
};
独立程序形式
#include <cstdio>
using namespace std;
const int N=1e5+10;
int e[N],l[N],r[N],idx;
void init(){
r[0]=1,l[1]=0,idx=2;
}
void add(int x){
e[idx]=x;
l[idx]=l[1],r[idx]=1;
r[l[1]]=idx,l[1]=idx++;
}
int remove(int k){
r[l[k]]=r[k],l[r[k]]=l[k];
return r[k];
}
int main(){
int n,m;
init();
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
add(i);
}
int s=n-1,pos=r[0];
while(s--){
int k=m-1;
while(k--){
pos=r[pos];
if(pos==1) pos=r[0];
}
pos=remove(pos);
if(pos==1) pos=r[0];
}
printf("%d\n",e[r[0]]);
return 0;
}
用bool数组解决
class Solution {
public:
int lastRemaining(int n, int m){
if(n==1) return 0; //特判
bool res[n]={0};
int t=m-1,s=0; //第一次用m-1,因为从0开始数
while(++s<n){ //共n-1次
t=t%n; //把t控制到n以内
res[t]=true; //标记
int k=m; //再次向后移动m次
while(k>0){
//这里是关键,因为数组的数并没真正删除,t保证移动到要删除的位置,k保证移动了m个有效数字
t++;
if(!res[t%n]) k--; //如果没有标记,k就减1
}
}
return t%n; //t可能大于n
}
};
用vector数组解决,直接删除
class Solution {
public:
int lastRemaining(int n, int m){
vector<int> table(n);
for(int i=0;i<n;i++) table[i]=i;
int pos=0; //用pos记录需要删除的位置
for(int i=0;i<n-1;i++){
pos=(pos+m-1)%table.size(); //计算每一个要删除的位置,vector的size函数时间复杂度是o(1)的。
table.erase(table.begin()+pos); //vector的删除操作时O(n),因为删除导致后面的数据前移1位。
}
return table[0];
}
};
DP求解
在《剑指offer》上对该问题从数学上分析出了一些规律。首先定义最初的n个数字(0,1,…,n-1)中最后剩下的数字是关于n和m的方程为f(n,m)。
在这n个数字中,第一个被删除的数字是(m-1)%n,为简单起见记为k。那么删除k之后的剩下n-1的数字为0,1,…,k-1,k+1,…,n-1,并且下一个开始计数的数字是k+1。相当于在剩下的序列中,k+1排到最前面,从而形成序列k+1,…,n-1,0,…k-1。该序列最后剩下的数字也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样(最初的序列是从0开始的连续序列),因此该函数不同于前面函数,记为f’(n-1,m)。最初序列最后剩下的数字f(n,m)一定是剩下序列的最后剩下数字f’(n-1,m),所以f(n,m)=f’(n-1,m)。
接下来我们把剩下的的这n-1个数字的序列k+1,…,n-1,0,…k-1作一个映射,映射的结果是形成一个从0到n-2的序列:
k+1 -> 0
k+2 -> 1
…
n-1 -> n-k-2
0 -> n-k-1
…
k-1 -> n-2
把映射定义为p,则p(x)= (x-k-1)%n,即如果映射前的数字是x,则映射后的数字是(x-k-1)%n。对应的逆映射是p-1(x)=(x+k+1)%n。
由于映射之后的序列和最初的序列有同样的形式,都是从0开始的连续序列,因此仍然可以用函数f来表示,记为f(n-1,m)。根据我们的映射规则,映射之前的序列最后剩下的数字f’(n-1,m)= p-1 [f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=(m-1)%n代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。
经过上面复杂的分析,我们终于找到一个递归的公式。要得到n个数字的序列的最后剩下的数字,只需要得到n-1个数字的序列的最后剩下的数字,并可以依此类推。当n=1时,也就是序列中开始只有一个数字0,那么很显然最后剩下的数字就是0。因此有递推公式:
当n=1时,f(n, m) = 0
当n>1时,f(n, m) = [f(n-1, m) +m] % n
因此就可以递归求解,复杂度为O(n)。
时间复杂度分析:O(n)
C++ 代码
class Solution {
public:
int lastRemaining(int n, int m){
if(n==1)
return 0;
else
return (lastRemaining(n-1,m)+m)%n;
}
};