圆圈中最后剩余的数字
原创
题目：
0,1,2,3 ，. . . ，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字，求这个圆圈里剩余的最后一个数字。
例如，0,1,2,3,4这5个数字组成的环中，从数字0开始每次删除第三个数字，那么依次删除的前四个数字就是：2,0,4,1
因此最后剩余的数字是3。
解法一：
直观的解法，将这环构造成一个环形链表。
首先，定义一个节点类作为数据类型。
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}将所有的数据放入一个环形的链表中，while循环用于找到要删除的节点为cur.next，cur用于记录待删除的节点的前导。注意这里的循环的退出的条件。
public int lastRemaining(int n,int m){
if (n<1 || m<1) return -1;
ListNode cur = new ListNode(0) ;
ListNode head = cur;
for (int i=1;i<n;i++){
cur.next = new ListNode(i);
cur = cur.next;
}
cur.next = head;
while (cur.next!=cur){
for (int i = 1 ; i< m;i++){
cur = cur.next;
}
cur.next = cur.next.next;
}
return cur.val;
}这个解法的算法复杂度为O(n*m);
解法二：
通过归纳得到规律，简化算法。推导过程参照《剑指offer》的45题。
public int lastRemaining(int n,int m){
if (n<1 || m<1) return -1;
int last = 0;
for (int i = 2;i<=n;i++){
last = (last+m)%i;
}
return last;
}这个算法的算法复杂度为O(n)。
总结：
在一些数学比较敏感的题目中，往往可以归纳出以一种简单的解法，避免使用大量的循环，当然解法一也是一种比较经典的思路，设计的环的问题，借用数据结构可以方便处理。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录