摘要

劍指 Offer 62. 圓圈中最后剩下的數(shù)字

一、約瑟夫環(huán)解析

題目中的要求可以表述為：給定一個(gè)長(zhǎng)度為 n 的序列，每次向后數(shù) m 個(gè)元素并刪除，那么最終留下的是第幾個(gè)元素？這個(gè)問題很難快速給出答案。但是同時(shí)也要看到，這個(gè)問題似乎有拆分為較小子問題的潛質(zhì)：如果我們知道對(duì)于一個(gè)長(zhǎng)度n - 1 的序列，留下的是第幾個(gè)元素，那么我們就可以由此計(jì)算出長(zhǎng)度為 n 的序列的答案。

我們將上述問題建模為函數(shù) f(n, m)，該函數(shù)的返回值為最終留下的元素的序號(hào)。

首先，長(zhǎng)度為n的序列會(huì)先刪除第m% n 個(gè)元素，然后剩下一個(gè)長(zhǎng)度為n - 1的序列。那么，我們可以遞歸地求解 f(n - 1, m)，就可以知道對(duì)于剩下的 n - 1 個(gè)元素，最終會(huì)留下第幾個(gè)元素，我們?cè)O(shè)答案為 x = f(n - 1, m)。

由于我們刪除了第 m % n 個(gè)元素，將序列的長(zhǎng)度變?yōu)?n - 1。當(dāng)我們知道了 f(n - 1, m) 對(duì)應(yīng)的答案 x 之后，我們也就可以知道，長(zhǎng)度為 n 的序列最后一個(gè)刪除的元素，應(yīng)當(dāng)是從 m % n 開始數(shù)的第 x 個(gè)元素。因此有 f(n, m) = (m % n + x) % n = (m + x) % n。

我們遞歸計(jì)算 f(n, m), f(n - 1, m), f(n - 2, m), ... 直到遞歸的終點(diǎn) f(1, m)。當(dāng)序列長(zhǎng)度為 1 時(shí)，一定會(huì)留下唯一的那個(gè)元素，它的編號(hào)為 0。

class Solution {public int lastRemaining(int n, int m) {return f(n, m);}public int f(int n, int m) {if (n == 1) {return 0;}int x = f(n - 1, m);return (m + x) % n;}
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，需要求解的函數(shù)值有n個(gè)。
• 空間復(fù)雜度：O(n)，函數(shù)的遞歸深度為n，需要使用 O(n)的?？臻g。

二、數(shù)學(xué) + 迭代

class Solution {public int lastRemaining(int n, int m) {int f = 0;for (int i = 2; i != n + 1; ++i) {f = (m + f) % i;}return f;}
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，需要求解的函數(shù)值有n個(gè)。

• 空間復(fù)雜度：O(1)，只使用常數(shù)個(gè)變量。

博文參考

《leetcode》