leetcode每日一题.面试题62:圆圈中最后剩下的数字

简介: leetcode每日一题.面试题62:圆圈中最后剩下的数字

题目描述:


0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


示例1:


输入: n = 5, m = 3
输出: 3


示例2:


输入: n = 10, m = 17
输出: 2


题目难度:简单


分析:

经典的约瑟夫环问题,很容易想到用模拟法去做,把所有的元素都放入List中,然后再根据下标删除,最后剩下的一个就是题目的答案。代码如下:


java:


class Solution {
    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>();
        // 首先把所有元素放入List中
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        // 用来记录前一次删除的下标,因为删除后并不是从头开始数的
        int prev = 0;
        // 可以用n代替List.size()
        while (n > 1) {
          // m+prev就是下一次需要删除的下标
          // 但它并不是从0开始数的,所以需要减1
          // 因为可能超出n的大小,所以需要对n取模
          // 因为n表示集合剩余元素的个数,所以需要减1
            prev = (m + prev - 1) % n--;
            list.remove(prev);
        }
        return list.get(0);
    }
}


进阶解法:


试想一下,如果我们知道了这个最后剩下的数的位置,那么是否可以反推出它在原数组中的位置呢?当然可以…因为最后只剩下一个数,那么下标当然是0了(废话)。那么我们用上面的公式反推看看:


就用例1,n=5,m=3,进行反推:
用x记录当前位置下标,n记录数组中的元素个数,此处不需要减1是因为只计算下标,不数数
公式:prev = (x + m) % n++
倒数第二:(0 + 3) % 2,求得prev = 1
倒数第三:(1 + 3) % 3,求得prev = 1
倒数第四:(1 + 3) % 4,求得prev = 0
倒数第五:(0 + 3) % 5,求得prev = 3


由上可看出:通过反推也可以确定未知数x在原数组中的位置,而数组中的数字是按照0,1,,n-1进行排列的,那么下标就等于元素的值。代码如下:


java:


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


python:


class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        x = 0
        for i in range(2, n + 1):
            x = (x + m) % i
        return x


总结:


在我使用模拟法时最先用到的数据结构并不是ArrayList,而是LinkedList,我理所当然的想到:涉及频繁删除的时候,应该用链表来做,效率更高。当我提交代码后却提示我代码运行超时,我本以为是此方法效率过慢(没考虑是LinkedList的问题)。然后我不死心又换成ArrayList,竟然过了,我就在想怎么和我理解的不一样,为什么如此频繁的删除操作,ArrayList竟然比LinkedList要快呢?于是我看了看它们两者的remove(int index)方法源码。


ArrayList:


public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}


LinkedList:


public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}


由源码可以知道:由于LinkedList在删除时首先会根据index去查找Node节点,虽然做了优化会根据index的大小决定从头遍历还是从尾遍历,但是必不可少的要去做一次遍历操作,时间复杂度为O ( n ),然后再通过Node节点去调用unlink(node)方法。而ArrayList是直接根据下标去确定元素的位置,时间复杂度为O ( 1 ) 然后移位只是内存中连续地址的copy而已,速度相比于LinkedList这种非连续的地址访问,当然要快了。

目录
相关文章
|
4月前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
4月前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
4月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
5月前
|
存储 算法 数据挖掘
深入解析力扣168题:Excel表列名称(进制转换法详解及模拟面试问答)
深入解析力扣168题:Excel表列名称(进制转换法详解及模拟面试问答)
|
5月前
|
存储 算法 数据挖掘
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
|
5月前
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
5月前
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
5月前
|
算法 数据挖掘 大数据
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
|
5月前
|
算法 数据挖掘 Java
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
深入解析力扣167题:两数之和 II(双指针法详解及模拟面试问答)
|
5月前
|
存储 算法 数据挖掘
【模拟面试问答】力扣165题:比较版本号(逐个比较与双指针法详解及模拟面试问答)
【模拟面试问答】力扣165题:比较版本号(逐个比较与双指针法详解及模拟面试问答)