摘要

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

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

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

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

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

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

我們遞歸計算 f(n, m), f(n - 1, m), f(n - 2, m), ... 直到遞歸的終點 f(1, m)。當序列長度為 1 時，一定會留下唯一的那個元素，它的編號為 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;}
}

復雜度分析

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

二、數(shù)學 + 迭代

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

復雜度分析

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

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

博文參考

《leetcode》