LEETCODE 390. Elimination Game 解题思路分析

题目大意:

消除游戏

给定一个从1 到 n 排序的整数列表。
首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。
第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。
我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。
返回长度为 n 的列表中,最后剩下的数字。

示例:

输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

输出:
6

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=390

解题思路分析:

本题的关在在于寻找数组变化的规律。首先,不论从左至右还是从右至左删除数字,每次删除操作后数组中元素的个数都会减半,当数组只剩下一个数字时,该数字就是我们最终的答案。换句话说,每当数组减半之后,我们需要观察剩余数组中首位元素的值,直到剩余数组长度为1时,这个首位元素的值即是返回结果。

因为最先从左侧开始删除,因此,原数组的首位元素(最左侧)一定是会被删除的。当从右侧开始删除时,数组首元素(最左侧)是否会被删除,取决于当前数组长度,如果数组长度是偶数,首元素不会被删除,否则首元素会被删除。比如1,2,3,4,5,从右侧删除时,5,3,1会被删除,而当个数为偶数时,比如1,2,3,4,这时我们只会删除4和2,首元素1不会被删除。

因此,数组首元素被删除的可能有两种,第一,从左侧开始删除。第二,从右侧开始删除并且数组长度为奇数。

当首元素被删除后,剩余数组的首元素就会变为它被删除前的下一个元素,那么问题来了,我们如何得知下一个元素是谁?其实并不难,因为数组中的数字是存在规律的,初始时,数组中每两个数字之间间隔为1,进行一次删除后,间隔变为2,再经过一次删除后间隔变为4,间隔会成倍增长。只要我们知道当前经过了多少次删除操作,就能算出,两数之间的间隔,从而也就能知道被删除首元素的下一个元素的值。

实现代码:

public int lastRemaining(int n) {
    // 数组中首元素
    int firstNum=1;
    // 数组中每两个数字间的差值
    int diff=1;
    // 是否为左起删除
    boolean isLeft=true;
    // 当元素个数大于1时,重复执行删除操作
    while(n>1){
        // 如果是左起删除,或者当前数组长度为奇数时,
        // 首元素会被删除掉
        if(isLeft || n%2==1){
            // 新的首元素将是原首元素相邻的下一元素
            firstNum+=diff;
        }
        // 删除操作后,数组元素个数减半
        n/=2;
        // 数组中相邻两数间的差值翻倍
        diff*=2;
        // 更换删除方向
        isLeft=!isLeft;
    }
    // 返回最后剩下的首元素
    return firstNum;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 54.75% of Java online submissions for Elimination Game.

Memory Usage: 37.6 MB, less than 33.33% of Java online submissions for Elimination Game.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-390-elimination-game-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。