我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 面試題62. 圓圈中最後剩下的數字

題目

0,1,,n-1這n個數字排成一個圓圈，從數字0開始，每次從這個圓圈裡刪除第m個數字。求出這個圓圈裡剩下的最後一個數字。

例如，0、1、2、3、4這5個數字組成一個圓圈，從數字0開始每次刪除第3個數字，則刪除的前4個數字依次是2、0、4、1，因此最後剩下的數字是3。

示例 1：

輸入: n = 5, m = 3
輸出: 3

示例 2：

輸入: n = 10, m = 17
輸出: 2

限制：

• 1 <= n <= 10^5
• 1 <= m <= 10^6

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

首先能想到的是模擬一個一個刪除，直到剩下最後一個，需要註意的一點是當剩下的n小於m時需要取模；
此類問題是約瑟夫環，所以可以直接用公式求解，至於原理和推導我就不班門弄斧了；

思路1-使用ArrayList，模擬刪除過程，註意剩餘總數n小於m時需要進行取模；

思路2-約瑟夫環的公式求解；

約瑟夫環

演算法源碼示例

package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ZhouJie
 * @date 2020年3月30日 下午9:18:03 
 * @Description: 面試題62. 圓圈中最後剩下的數字
 *
 */
public class LeetCode_Offer_62 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年3月30日 下午9:17:57 
	 * @param: @param n
	 * @param: @param m
	 * @param: @return
	 * @return: int
	 * @Description: 1-模擬刪除過程
	 *
	 */
	public int lastRemaining_1(int n, int m) {
		List<Integer> all = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			all.add(i);
		}
		int winner = 0;
		while (n > 1) {
			// 每次刪除第m個位置的數，對應索引為m-1，直至n為1，即只剩一個數
			winner = (winner + m - 1) % n;
			all.remove(winner);
			n--;
		}
		return all.get(0);
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年3月30日 下午9:34:57 
	 * @param: @param n
	 * @param: @param m
	 * @param: @return
	 * @return: int
	 * @Description: 2-本題為約瑟夫環類問題，數學公式解決；
	 *
	 */
	public int lastRemaining_2(int n, int m) {
		int winner = 0;
		// 從剩餘兩個數的時候反推到n個數
		for (int i = 2; i <= n; i++) {
			winner = (winner + m) % i;
		}
		return winner;
	}
}