leetcode 剑指 Offer 62. 圆圈中最后剩下的数字

剑指 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
输出: 2

限制：

1 <= n <= 10^5
1 <= m <= 10^6

思路参考：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/

思路一：使用ArrayList

使用一个arrayList存储所有元素的下标,把所有元素下标都删了之后，只剩下一个元素，这时get(0)就获取到了最终的结果.

其实删除了当前元素后下个需要被删除的元素的位置是可以计算出来的，不需要模拟，这太费时间了。

假设当前删除的位置是 idxidx，下一个删除的数字的位置是 idx + midx+m 。但是，由于把当前位置的数字删除了，后面的数字会前移一位，所以实际的下一个位置是 idx + m - 1idx+m−1。由于数到末尾会从头继续数，所以最后取模一下，就是 (idx + m - 1) pmod n(idx+m−1)(modn)。

idx = (idx + m - 1) % n; 就可以得到下一个要被删除的元素的位置

 1 class Solution {
 2     public int lastRemaining(int n, int m) {
 3 
 4         ArrayList<Integer> list = new ArrayList<Integer>();
 5         for(int i = 0; i < n; i++){
 6             list.add(i);
 7         }
 8         int idx = 0;
 9         while(n > 1){
10             idx = (idx + m - 1) % n;
11             list.remove(idx);
12             n--;        // 删除一个元素后，数组容量减一
13         }
14         return list.get(0);
15     }
16 }

leetcode 运行时间为：1102 ms > 9.33%，空间为40.8 MB > 18.84%

复杂度分析：

时间复杂度：每次循环删除一个元素的复杂度为O(n), 一共循环了 n- 1次，所以时间复杂度为O(n²)

空间复杂度：借助了一个ArrayList列表，最大大小为n，所以空间复杂度为O(n)

思路二：数学推导

最后只剩下一个元素，假设这个最后存活的元素为 num, 这个元素最终的的下标一定是0 （因为最后只剩这一个元素），所以如果我们可以推出上一轮次中这个num的下标，然后根据上一轮num的下标推断出上上一轮num的下标，直到推断出元素个数为n的那一轮num的下标，那我们就可以根据这个下标获取到最终的元素了。推断过程如下：

首先最后一轮中num的下标一定是0，这个是已知的。

那上一轮应该是有两个元素，此轮次中 num 的下标为 (0 + m)%n = (0+3)%2 = 1; 说明这一轮删除之前num的下标为1；

再上一轮应该有3个元素，此轮次中 num 的下标为 (1+3)%3 = 1；说明这一轮某元素被删除之前num的下标为1；

再上一轮应该有4个元素，此轮次中 num 的下标为 (1+3)%4 = 0；说明这一轮某元素被删除之前num的下标为0；

再上一轮应该有5个元素，此轮次中 num 的下标为 (0+3)%5 = 3；说明这一轮某元素被删除之前num的下标为3；

....

因为我们要删除的序列为0-n-1, 所以求得下标其实就是求得了最终的结果。比如当n 为5的时候，num的初始下标为3，所以num就是3，也就是说从0-n-1的序列中，经过n-1轮的淘汰，3这个元素最终存活下来了，也是最终的结果。

总结一下推导公式：(此轮过后的num下标 + m) % 上轮元素个数 = 上轮num的下标

1 class Solution {
2     public int lastRemaining(int n, int m) {
3         int idx  = 0;       // 最后一轮后num的下标为0
4         for(int i = 2; i <= n; i++){    // 倒数第二轮应该有2个元素，所以从2开始迭代
5             idx = (idx + m) % i;
6         }
7         return idx;
8     }
9 }

leetcode 运行时间为7ms, 空间为35.6 MB

复杂度分析：

时间复杂度：很容易看出来，只有一个for循环，所以时间复杂度为O(n)

空间复杂度：O(1)