圆圈中最后剩余的数字

题目:

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)。

总结:

在一些数学比较敏感的题目中,往往可以归纳出以一种简单的解法,避免使用大量的循环,当然解法一也是一种比较经典的思路,设计的环的问题,借用数据结构可以方便处理。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏owent

最长单调子序列 复杂度nlog(n)

791
来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

1934
来自专栏深度学习与计算机视觉

算法-获取链表中倒数第k个结点

题目: 输入一个链表,输出该链表中的倒数第k个结点。比如链表中的值为1,2,3,4,5,6。倒数第三个结点为值为4的结点。链表定义如下: struct Li...

1828
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

1993
来自专栏小樱的经验随笔

51 Nod 1791 合法括号子段【分治+字符串】

1791 合法括号子段 基准时间限制:1 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 有一个括号序列,现在要计算一下它有多少非空子段是合法...

3026
来自专栏书山有路勤为径

包含min函数的栈

LeetCode 155. Min Stack 设计一个栈,支持如下操作,这些操作的算法复杂度需要是常数级,O(1) 1.push(x) : 将元素x压入...

1031
来自专栏小樱的经验随笔

UVA 11636-Hello World!(水题,猜结论) UVA11636-Hello World!

UVA11636-Hello World! Time limit: 1.000 seconds When you first made the computer ...

3664
来自专栏韦弦的偶尔分享

Swift 旋转数组 - LeetCode

例如,如果 n = 7 , k = 3,给定数组 [1,2,3,4,5,6,7] ,向右旋转后的结果为 [5,6,7,1,2,3,4]。

1685
来自专栏书山有路勤为径

递归函数基础

函数代码中调用自己时称为递归,该函数被称为递归函数。递归函数是一个很高效的 开发技巧,可以极大的简化代码提高开发效率。递归函数与循环类似,循环可以完成的 事情,...

943
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

782

扫码关注云+社区

领取腾讯云代金券