《剑指Offer》62：圆圈中最后剩下的数字（约瑟夫环）

题目

0,1,2…,n-1这n个数字排成一个圆圈，从数字0开始，每次从这圆圈你删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次2、0、4、1，因此最后剩下的数字是3。

本题就是有名的约瑟夫（Josephuse）环问题。

分析

两种解题方法：

1. 用环形链表模拟圆圈的经典解法
2. 分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字

放码

一

用环形链表模拟圆圈的经典解法

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

二

分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字

首先我们定义一个关于 n 和 m 的方程f(n,m)，表示每次在 n 个数字 0，1， … ，n-1中每次删除第 m 个数字最后剩下的数字。

在这 n个数字中，第一个被删除的数字是(m-1)%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，1，… ，k-1 。

该序列最后剩下的数字也应该是关于 n 和 m 的函数。由于这个序列的规律和前面最初的序列不一样（最初的序列是从 0 开始的连续序列），因此该函数不同于前面的函数，记为 f’(n-1,m)。

最初序列最后剩下的数字 f(n, m）一定是删除一个数字之后的序列最后剩下的数字，即 f(n, m)=f'(n-1, m）。

接下来我们把剩下的这 n-1 个数字的序列 k-1， …，n-1，0，1，… ，k-1 做一个映射，映射的结果是形成一个从 0 到 n-2 的序列：

我们把映射定义为p，则p(x)=(x-k-1)%n if p(x)<0, then p(x)+=n。

它表示如果映射前的数字是x，那么映射后的数字是(x-k-1)%n。该映射的逆映射是p⁻¹(x)=(x+k+1)%n。

由于映射之后的序列和最初的序列具有同样的形式，即都是从0开始的连续序列，因此仍然可以用函数f来表示，记为f(n-1, m)。根据我们的映射规则，映射之前的序列中最后剩下的数字f'(n-1, m)=p⁻¹[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。我们把这种关系表示为:

public int lastRemaining2(int n, int m) {
	if(n < 1 || m < 1) {
		throw new IllegalArgumentException();
	}
	return n == 1 ? 0 : (lastRemaining2(n - 1, m) + m) % n;
}

三

针对这个题目，先说说难点：

数字组成是环形的结构，当数到最后个数字时，还不是需要删除的第 m 个数，需要回至数组的首位继续；
每次重新数的位置，都是上次删除数字的下一位。
针对第一个难点，可以考虑取模；

针对第二个难点，可以考虑将删除数字下一位，作为下次重新数的起点，剩余数字依次排列。（注意数字组成是环状的）

考虑先模拟，然后再进行逆推：

（为体现闭环，这里将数组进行复制。注意： 未得到最后 1 位数时，除第 1 轮开始 ，每一轮都是以上一轮删除数字下一位作为起点，重新数需要删除的第 m 个数）

这就是模拟之后得到的结果。

现在我们来进行逆推：

最终确定的 1 个数字，这个数字对应的索引一定是 0，逆推这个最终数字在每一轮中所处的索引位置，那么假设（n 表示数组元素个数，m 表示要删除的第 m 个数，取示例 1，n = 5， m = 3）：

• n = 1 时，索引：0；
• n = 2 时，索引：(0 + m) % 2 = 3 % 2 = 1；
• n = 3 时，索引：((0 + m) % 2 + 3) % 3 = (1 + 3) % 3 = 1；
• n = 4 时，索引：(((0 + m) % 2 + 3) % 3 + m) % 4 = (1 + 3) % 4 = 0；
• n = 5 时，索引：((((0 + m) % 2 + 3) % 3 + m) % 4 + m) % 5 = (0 + 3) % 5 = 3 。

大致讲下前面的逆推过程，找出剩余元素在前面每一轮所处的位置：

• 当剩下 1 个数字的时候，这个数字（3）的索引为 0；
• 往前逆推，当剩下 2 个数字的时候，在上一轮元素索引的基础上，要补上 m 个位置，然后对数组元素个数取模，得到这一轮该元素所在的位置，代入 n，m，可得数字（3）索引为 1；
• 当剩下 3 个数字时，同样补上 m 个位置，然后对数组元素个数取模（这个时候数组元素个数为 3），代入 m，n，得数字（3）索引为 1；
• …

对上面的逆推过程进行总结：从最后 1 轮往前逆推时，前面一轮的元素所处的位置为，（当前索引 + m） % 前面一轮元素个数。

那么根据这个公式，用代码进行实现。

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        ans = 0
        # 最后 1 位为最终保留数字
        # 往前逆推，从元素个数为 2 开始
        for i in range(2, n + 1):
            # 逆推公式
            ans = (ans + m) % i

        return ans

测试

import org.junit.Assert;
import org.junit.Test;

public class LastRemainingTest {

	@Test
	public void test() {
		LastRemaining lr = new LastRemaining();
		
		Assert.assertEquals(3, lr.lastRemaining(5, 3));
		Assert.assertEquals(2, lr.lastRemaining(10, 17));
		Assert.assertEquals(3, lr.lastRemaining2(5, 3));
		Assert.assertEquals(2, lr.lastRemaining2(10, 17));
	}
	
}

参考

1. LeetCode 面试题62. 圆圈中最后剩下的数字

2. LaTex数学公式生成