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

忘是亡心i 2023-07-19 10:55 9阅读 0赞

### 题目描述： ###

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 ) O(n) O(n)，然后再通过`Node`节点去调用`unlink(node)`方法。而`ArrayList`是直接根据下标去确定元素的位置，时间复杂度为 O ( 1 ) O(1) O(1)然后移位只是内存中连续地址的copy而已，速度相比于`LinkedList`这种非连续的地址访问，当然要快了。