題目描述：0,1,,n-1 這 n 個數字排成一個圓圈，從數字 0 開始，每次從這個圓圈裡删除第 m 個數字。求出這個圓圈裡剩下的最後一個數字。例如，0、1、2、3、4 這 5 個數字組成一個圓圈，從數字 0 開始每次删除第 3 個數字，則删除的前 4 個數字依次是 2、0、4、1，是以最後剩下的數字是 3。
示例：
輸入: n = 5, m = 3
輸出: 3 複制
解法 1: 數學規律
可以發現：
- n=1，最後剩下的數字是 0
- n=2，最後剩下的數字是 (0 + m)%2
- n=3，最後剩下的數字是 ((0 + m)%2 + m)%3
可以将上面的規律寫成循環，第 n 次的結果等于：(上次一次結果 + m)%n
代碼實作如下：
// ac位址：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
// 原文位址：https://xxoo521.com/2020-04-19-last-remain-number/
/**
* @param {number} n
* @param {number} m
* @return {number}
*/
var lastRemaining = function(n, m) {
let result = 0;
for (let i = 2; i <= n; ++i) {
result = (result + m) % i;
}
return result;
}; 複制
時間複雜度是O(N)，空間複雜度是O(1)。
解法 2：模拟循環連結清單
嘗試了下這種做法，會 TLE。因為時間複雜度是 O(m*n)。
本文參與 騰訊雲自媒體分享計劃 ，歡迎熱愛寫作的你一起參與！
本文分享自作者個人站點/部落格
https://xxoo521.com/
複制
如有侵權，請聯系 [email protected] 删除。