AlgoPressAppearance
62-圆圈中最后剩下的数字
题目描述
https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
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
思路：模拟(超时)
模拟法，遍历从圆圈中删除该数字，标记为0，然后轮询直到剩余一个数字 应该有数学公式计算的，暂时不知道。
- 代码：数组直接模拟，会超时
csharp
public class Solution {
public int LastRemaining(int n, int m) {
if(m>n){
return 0;
}
int index = 0; //数组的index
int delIndex = 0;
int deleted = 0; //删除掉的数字个数
int[] nums = new int[n];
while(deleted < n-1){
if(nums[index] == 0){
index++;
index = index % n;
continue;
}
else{
if(delIndex == m-1){ //删除
Console.WriteLine("deleted {0}",delIndex);
nums[index] = 0;
deleted++;
}
delIndex++;
delIndex = delIndex % m;
index++;
index = index % n;
}
}
//只剩一个数
int num = 0;
for(int i=0; i<nums.Length; i++){
if(nums[i] != 0){
num = nums[i];
break;
}
}
return num;
}
}
- 代码 ArrayList直接模拟 ： 仍然会超时
csharp
public class Solution {
public int LastRemaining(int n, int m) {
List<int> list = new List<int>();
for(int i=0; i<n; i++){
list.Add(i);
}
int index = 0;
while(n > 1){
index = (index + m - 1) % n;
list.RemoveAt(index);
n--;
}
return list[0];
}
}
根据题目n,m的数据规模， O(n*m) = 10^11 会超时
思路2：递归
- 定义 f(n,m) 是返回最后一个存在的索引。 长度为n的序列，会先删除 m%n 位置的元素，然后剩下长度为 n-1 的序列。 那么可以递归求解 f(n-1,m)，就可以知道对于剩下的 n-1 个元素，最终会留下第几个元素，我们设答案为 x = f(n-1,m)
由于我们删除了第 m % n 个元素， 将序列变成了 n-1，当我们知道 f(n-1,m)对应的答案 x 之后, 我们也可以知道，长度为 n 的序列最后一个删除的元素，应该是 m % n 开始数的第 x 个元素。
因此有 f(n,m) = (m % n + x) % n = (m + x) % n;
还是不很好理解
csharp
public class Solution {
public int LastRemaining(int n, int m) {
if(n == 1){
return 0;
}
int x = LastRemaining(n-1,m);
return (x + m) % n;
}
}
思路2：迭代法
假设 m = 3;
如果只有1个人活着，那么他的下标是 0 ，因为只有一个数字了， n=1 如果此时有2个人，那么上面活着的人，他的下标是多少呢。 (0 + 3) % 2 = 1 ，因为此时被他删掉的人的是从他的下标开始数m个 % n 删掉的 如果此时有3个人，那么上面活着的人，他的小标是多少呢、 (1 + 3) % 3 = 1
f(2,m) = (f(1,m) + m)%n = (0+m)%n
csharp
public class Solution{
public int LastRemaining(int n, int m){
int ans = 0;
for(int i=2; i<=n; i++){
ans = (ans + m) % i;
}
return ans;
}
}