1.题目

2.思路

可以使用一个环形链表模拟（但是会超时），可以使用灰常巧妙的数学逆推思想：

（1）【最后一轮】无论怎样，最后都是只剩下一个元素——可以假设该最后存活的数值为num，且这个元素在数组中的下标一定是0（因为只有1个元素）。

（2）【上一轮】是有2个元素，在这轮中num的下标为$(0+m)$%$n$=$(0+3)$%2=1——说明这一轮删除之前num的下标为1，再次强调！！这个num可理解为若只有2个数（n=2）时，最后存活的元素所在当前轮数组中的下标。

（3）【再上一轮】是有3个元素，num的下标为 (1+3)%3 = 1，即该轮某元素被删前的num下标为1。

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

（5）【再上一轮】应该有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的下标

法二：动态规划

3.代码

class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n==1){
            return 0;
        }
        int ans=0;
        for(int i=2;i<=n;i++){
            ans=(ans+m)%i;
        }
        return ans;
    }
};

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

4.reference

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/

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/114108303