劍指offer | 面試題49：圓圈中最後剩下的數字

死磕算法系列文章

幹貨 | 手撕十大經典排序算法
劍指offer | 認識面試
劍指offer | 面試題2：實作Singleton模式
劍指offer | 面試題3：二維數組的查找
劍指offer | 面試題4：替換空格
劍指offer | 面試題5：從尾到頭列印連結清單
劍指offer | 面試題6：重建二叉樹
劍指offer | 面試題7：用兩個棧實作隊列
劍指offer | 面試題8：旋轉數組的最小數字
劍指offer | 面試題9：斐波那契數列
劍指offer | 面試題10：青蛙跳台階問題
劍指offer | 面試題11：矩陣覆寫
劍指offer | 面試題12：二進制中1的個數
劍指offer | 面試題13：數值的整數次方
劍指offer | 面試題14：列印從1到最大的n位數
劍指offer | 面試題15：删除連結清單的節點
劍指offer | 面試題16：将數組中的奇數放在偶數前
劍指offer | 面試題17：連結清單中倒數第k個節點
劍指offer | 面試題18：反轉連結清單
劍指offer | 面試題19：合并兩個有序連結清單
劍指offer | 面試題20：判斷二叉樹A中是否包含子樹B
劍指offer | 面試題21：二叉樹的鏡像
劍指offer | 面試題22：順時針列印矩陣
劍指offer | 面試題23：包含min函數的棧
劍指offer | 面試題24：棧的壓入、彈出序列
劍指offer | 面試題25：從上到下列印二叉樹
劍指offer | 面試題26：二叉搜尋樹的後序周遊序列
劍指offer | 面試題27：二叉樹中和為某一值的路徑
劍指offer | 面試題28：複雜連結清單的複制
劍指offer | 面試題29：二叉搜尋樹轉換為雙向連結清單
劍指offer | 面試題30：字元串的排列
劍指offer | 面試題31：數組中出現次數超過一半的數字
劍指offer | 面試題32：最小的k個數
劍指offer | 面試題33：連續子數組的最大和
劍指offer | 面試題34：1～n 整數中 1 出現的次數
劍指offer | 面試題35：把數組排成最小的數
劍指offer | 面試題36：醜數
劍指offer | 面試題37：第一個隻出現一次的字元
劍指offer | 面試題38：數組中的逆序對
劍指offer | 面試題39：兩個連結清單的第一個公共節點
劍指offer | 面試題40：數組中數字出現的次數
劍指offer | 面試題41：二叉樹的深度
劍指offer | 面試題42：平衡二叉樹
劍指offer | 面試題43：和為s的兩個數字
劍指offer | 面試題44：和為s的連續整數序列
劍指offer | 面試題45：翻轉單詞順序
劍指offer | 面試題46：左旋轉字元串
劍指offer | 面試題47：n個骰子的點數
劍指offer | 面試題48：撲克牌中的順子

“Leetcode : https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_49_lastRemaining/Solution.java

劍指 Offer 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
輸出:

複制

利用公式法：f[n] = (f[n-1] + k) mod n，或使用循環連結清單實作

“來吧，一圖勝千言。如下圖所示，為 n = 5 , m = 3 時的狀态轉移和對應的模拟删除過程。

複雜度分析：

時間複雜度 O(n)：狀态轉移循環 n - 1 次使用 O(n) 時間，狀态轉移方程計算使用 O(1) 時間；
空間複雜度 O(1) ：使用常數大小的額外空間；

package com.nateshao.sword_offer.topic_49_lastRemaining;

/**
 * @date Created by 邵桐傑 on 2022/2/24 21:51
 * @微信公衆号 千羽的程式設計時光
 * @個人網站 www.nateshao.cn
 * @部落格 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int i = lastRemaining(5, 3);
        System.out.println("i = " + i);
    }
    public static int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            // i 個人時删除數的索引等于 i-1 個人時删除數的索引+k(再對i 取餘)
            x = (x + m) % i;
        }
        return x;
    }
}

複制

參考文章：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow