面試題62. 圓圈中最后剩下的數(shù)字
題目來(lái)源：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
題目
0,1,,n-1這n個(gè)數(shù)字排成一個(gè)圓圈浪汪，從數(shù)字0開(kāi)始，每次從這個(gè)圓圈里刪除第m個(gè)數(shù)字玷犹。求出這個(gè)圓圈里剩下的最后一個(gè)數(shù)字隔披。
例如，0鸠姨、1铜秆、2、3讶迁、4這5個(gè)數(shù)字組成一個(gè)圓圈连茧，從數(shù)字0開(kāi)始每次刪除第3個(gè)數(shù)字，則刪除的前4個(gè)數(shù)字依次是2、0啸驯、4客扎、1，因此最后剩下的數(shù)字是3罚斗。
示例 1：
輸入: n = 5, m = 3
輸出: 3
示例 2：
輸入: n = 10, m = 17
輸出: 2
限制：
- 1 <= n <= 10^5
- 1 <= m <= 10^6
解題思路
思路：數(shù)學(xué)解法虐唠。（逆推）
這道題目屬于約瑟夫環(huán)問(wèn)題。（有點(diǎn)像丟手絹惰聂，攤手）
針對(duì)這個(gè)題目疆偿，先說(shuō)說(shuō)難點(diǎn)：
- 數(shù)字組成是環(huán)形的結(jié)構(gòu)，當(dāng)數(shù)到最后個(gè)數(shù)字時(shí)搓幌，還不是需要?jiǎng)h除的第 m 個(gè)數(shù)杆故，需要回至數(shù)組的首位繼續(xù)；
- 每次重新數(shù)的位置溉愁，都是上次刪除數(shù)字的下一位处铛。
針對(duì)第一個(gè)難點(diǎn)，可以考慮取模拐揭；
針對(duì)第二個(gè)難點(diǎn)撤蟆，可以考慮將刪除數(shù)字下一位，作為下次重新數(shù)的起點(diǎn)堂污，剩余數(shù)字依次排列家肯。（注意數(shù)字組成是環(huán)狀的）
考慮先模擬，然后再進(jìn)行逆推：
（為體現(xiàn)閉環(huán)盟猖，這里將數(shù)組進(jìn)行復(fù)制讨衣。注意： 未得到最后 1 位數(shù)時(shí)，除第 1 輪開(kāi)始 式镐，每一輪都是以上一輪刪除數(shù)字下一位作為起點(diǎn)反镇，重新數(shù)需要?jiǎng)h除的第 m 個(gè)數(shù)）
這就是模擬之后得到的結(jié)果。
現(xiàn)在我們來(lái)進(jìn)行逆推：
最終確定的 1 個(gè)數(shù)字娘汞，這個(gè)數(shù)字對(duì)應(yīng)的索引一定是 0歹茶，逆推這個(gè)最終數(shù)字在每一輪中所處的索引位置，那么假設(shè)（n 表示數(shù)組元素個(gè)數(shù)你弦，m 表示要?jiǎng)h除的第 m 個(gè)數(shù)惊豺，取示例 1，n = 5鳖目， m = 3）：
- n = 1 時(shí)扮叨，索引：0；
- n = 2 時(shí)领迈，索引：(0 + m) % 2；
- n = 3 時(shí)，索引：((0 + m) % 2 + 3) % 3狸捅；
- n = 4 時(shí)衷蜓，索引：(((0 + m) % 2 + 3) % 3 + m) % 4；
- n = 5 時(shí)尘喝，索引：((((0 + m) % 2 + 3) % 3 + m) % 4 + m) % 5磁浇。
大致講下前面的逆推過(guò)程，找出剩余元素在前面每一輪所處的位置：
- 當(dāng)剩下 1 個(gè)數(shù)字的時(shí)候朽褪，這個(gè)數(shù)字的索引為 0置吓；
- 往前逆推，當(dāng)剩下 2 個(gè)數(shù)字的時(shí)候缔赠，在上一輪元素索引的基礎(chǔ)上衍锚，要補(bǔ)上 m 個(gè)位置，然后對(duì)數(shù)組元素個(gè)數(shù)取模嗤堰，得到這一輪該元素所在的位置戴质，代入 n，m踢匣，可得索引為 1告匠；
- 當(dāng)剩下 3 個(gè)數(shù)字時(shí)，同樣補(bǔ)上 m 個(gè)位置离唬，然后對(duì)數(shù)組元素個(gè)數(shù)取模（這個(gè)時(shí)候數(shù)組元素個(gè)數(shù)為 3）后专，代入 m，n输莺，得索引為 1行贪；
- ...
對(duì)上面的逆推過(guò)程進(jìn)行總結(jié)：從最后 1 輪往前逆推時(shí)，前面一輪的元素所處的位置為模闲，（當(dāng)前索引 + m） % 前面一輪元素個(gè)數(shù)建瘫。
那么根據(jù)這個(gè)公式，用代碼進(jìn)行實(shí)現(xiàn)尸折。
代碼實(shí)現(xiàn)
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
ans = 0
# 最后 1 位為最終保留數(shù)字
# 往前逆推啰脚，從元素個(gè)數(shù)為 2 開(kāi)始
for i in range(2, n + 1):
# 逆推公式
ans = (ans + m) % i
return ans
實(shí)現(xiàn)結(jié)果
以上就是通過(guò)數(shù)學(xué)解法進(jìn)行逆推，進(jìn)而解決《面試題62. 圓圈中最后剩下的數(shù)字》問(wèn)題的主要內(nèi)容实夹。
歡迎關(guān)注微信公眾號(hào)《書(shū)所集錄》
