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

╰+攻爆jí腚メ 2022-12-12 13:38 114阅读 0赞

## 题目 ##

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

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

![74f2bd934a6d996adea8a4c61c01b2e6.png][]

本题就是有名的约瑟夫（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 的序列：

<table> 
 <thead> 
  <tr> 
   <th>last index</th> 
   <th>-&gt;</th> 
   <th>index</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>k+1</td> 
   <td></td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>k+2</td> 
   <td></td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td></td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>n-1</td> 
   <td></td> 
   <td>n-k-2</td> 
  </tr> 
  <tr> 
   <td>0</td> 
   <td></td> 
   <td>n-k-1</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td></td> 
   <td>n-k</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td></td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>k-1</td> 
   <td></td> 
   <td>n-2</td> 
  </tr> 
 </tbody> 
</table>

我们把映射定义为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。我们把这种关系表示为:

![66ca493f84101a6a9dd254d89a082a75.png][]

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;
    }

![n=5,m=3的推导过程][n_5_m_3]

### 三 ###

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

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

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

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

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

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

现在我们来进行逆推：

![2930c149cc61056273af35c9c601edd8.png][]

最终确定的 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. 圆圈中最后剩下的数字][LeetCode _62.]
2.  [LaTex数学公式生成][LaTex]

[74f2bd934a6d996adea8a4c61c01b2e6.png]: /images/20221123/5444abdeeed64a7a8b1bec35d2dbde16.png
[66ca493f84101a6a9dd254d89a082a75.png]: /images/20221123/3cf7222612f844df8295ad09e4da5dc6.png
[n_5_m_3]: /images/20221123/ad551fa07ee84053b39988bea8d57add.png
[2930c149cc61056273af35c9c601edd8.png]: /images/20221123/e49792f005d446f2ac65892d75d6135a.png
[LeetCode _62.]: https://mp.weixin.qq.com/s/Lk536k3C68I7p82k_JPQIw
[LaTex]: https://latex.91maths.com/s/?JTVDYmVnaW4lN0JlcXVhdGlvbiU3RCUwQWYobiUyQ20pJTNEJTBBJTVDYmVnaW4lN0JjYXNlcyU3RCUwQTAlMjYlMjAlNUN0ZXh0JTdCbiUzRDElN0QlNUMlNUMlMEElNUJmKG4tMSUyQ20pJTJCbSU1RCU1QyUyNW4lMjYlMjAlNUN0ZXh0JTdCbiUzRTElN0QlMEElNUNlbmQlN0JjYXNlcyU3RCUwQSU1Q2VuZCU3QmVxdWF0aW9uJTdEJTBB