圆圈中最后剩余的数字

原创

大学里的混子

修改于 2018-10-30 20:41:53

1.3K0

修改于 2018-10-30 20:41:53

文章被收录于专栏：LeetCode

题目：

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 删除。

编程算法

登录后参与评论

0 条评论

热度