logo头像

野渡's小小知识乐园

4.约瑟夫环问题

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。人都有求生的欲望,问谁是最后一个死?

1、题目:孩子们的游戏(圆圈中最后剩下的数)


题目原链接:https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

2、题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

3、解题思路

解法一:循环链表模拟解决

既然是一个圆圈,我们很自然就能想到用一个环形链表来进行模拟。创建一个共有n个节点的环形链表, 依次遍历链表删除节点第m个节点,然后继续遍历直到链表中只有一个节点为止。需要注意的是,每一次到达链表尾端的时候都将指针调整到指向第一个节点,从而形成环。

为了能快速实现代码,用标准模板库的std::list实现就是一个很好的选择。这种解决方案没删除一个数需要遍历m次,所以时间复杂度为O(mn),空间复杂度为O(n)。实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(m==0 ||n==0) return -1;
if(n==1) return 1;

list<int> number;
int i,cnt{0};
for(i=0;i<n;i++) number.push_back(i);
list<int>::iterator iter=number.begin();
while(number.size()!=1)
{
if(cnt==m-1)
{
number.erase(iter++);
cnt=0;
}
else iter++,cnt++;
if(iter==number.end()) iter=number.begin(); //调整
}
return *number.begin();
}
};

解法二:数学分析、寻找规律

假设现在有6个人,计数为3,则:
(1)第一次删除

1
2
编号: 0 1 2 3 4 5 
计数: 0 1 2 0 1 2

可以看出,第一次选中去掉第3个人,编号2。

(2)第二次删除
剩下的人从新编号:

1
2
3
原编号:    0 1 2 3 4 5 
第一次编号:3 4 X 0 1 2 => 0 1 2 3 4
计数: 0 1 2 0 1

可以看出,第二次选中去掉新编号中的第3个人,新编号为2,同时也知道原编号为5。

(3)第5(n-1)次删除
到第5次删除的时候后,将只剩下一个数,即是我们要求的数:

1
2
3
4
5
6
原编号:    0 1 2 3 4 5
第一次编号:3 4 X 0 1 2
第二次编号:0 1 X 0 2 X
第三次编号:1 2 X X 0 X
第四次编号:1 X X X 0 X => 0 1
计数: (0)2 1

可以看出第5次删除选中了第4次编号的第1个人,编号为0,对应的原编号为4。

从上面的关系中,我们可以看出,每一次的新编号和上次的编号之间存在映射关系:

1
2
new_number=(old_number-m)%上次编号总人数    
=> old_number=(new_number+m)%上次编号总人数

由于最后只剩下一个人,其new_number明显应该为0,我们可以=>其第四次编号为1=>其第三次编号为1=>其第二次编号为0=>其第一次编号为3=>原编号为0。故最后剩下的人为第1个,编号为0。

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(m<1 || n<1) return -1;//考虑异常情况
if(n==1) return 0;

int result=0;//最后剩下的数新编号为0
for(int i=2;i<=n;i++)
{
result=(result+m)%i;
}
return result;
}
};