ChunNote
0%

leetCode-390:Elimination Game

发表于 分类于

问题描述

给定一个正整数 n，表示存在 [1, n] 的整数数组，要求对数组进行以下操作：

  • 从左到右，间隔删除元素
  • 从右到左，间隔删除元素
  • 重复以上操作直到数组剩下最后一个元素

返回数组剩下的最后元素。题目链接：点我

样例输入输出

输入：9

输出：6

解释：原始数组：[1, 2, 3, 4, 5, 6, 7, 8, 9]

第一次从左向右间隔删除元素 1、3、5、7、9，数组变为 [2, 4, 6, 8]

第二次从右向左间隔删除元素 8、4，数组变为 [2, 6]

第三次从左向右间隔删除元素 2，数组变为 [6]

此时数组仅剩下最后一个元素，故返回数字 6

输入：1

输出：1

问题解法

如果直接构造数组然后遍历一个一个删除，肯定会超时。需要找到更优化的做法，此做法参考：https://leetcode.com/problems/elimination-game/solutions/87119/JAVA:-Easiest-solution-O(logN)-with-explanation/。主要思想是记录每次数组首元素、数组剩余长度、数组时从左向右删除还是从右向左删除。当数组剩下最后一个元素时，将首元素返回。

当删除元素是从左向右删除时，数组首元素会删除（发生变化），数组首元素 head = head + step，step 表示元素之间的间隔（每次数组都是一个等差数列，相邻两个元素之间的间隔时一样的），数组剩余元素个数变为一半。

当删除元素时从右向左删除时，如果数组元素个数是奇数（比如：[2, 4, 6]），那么首元素会发生变化，如果是偶数（比如：[2, 4, 6, 8]），首元素不变。同样，删除后，数组剩余个数变为一半。

举例说明如下：假设 n = 24 ，则初始数组为 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]。此时 head = 1, step = 1，count = 24。

  • 第一次，数组从左向右删除，数组首元素被删除，发生变化，变为 head = head + step = 1 + 1 = 2，数组剩余个数 count = count / 2 = 12，step = step * 2 = 1 * 2 = 2 （为什么是乘 2，因为数组每次都是等差数列，每次间隔删除元素，删除后相邻元素的差值就是上次相邻元素差值的 2 倍），此时数组变为 [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
  • 第二次，数组从右向左删除，因为元素个数是 12，偶数，数组首元素不变，仍然为 2，step = step * 2 = 2 * 2 = 4，数组剩余元素 count = count / 2 = 12 / 2 = 6，此时数组变为 [2, 6, 10, 14, 18, 22]
  • 第三次，数组从左向右删除，数组首元素被删除，发生变化，变为 head = head + step = 2 + 4 = 6，数组剩余个数 count = count / 2 = 6 / 2 = 3, step = step * 2 = 4 * 2 = 8，此时数组变为 [6, 14, 22]
  • 第四次，数组从右向左删除，因为元素个数是 3，奇数，数组元素发生变化，变为 head = head + step = 6 + 8 = 14，数组剩余个数 count = count / 2 = 3 / 2 = 1，step = step * 2 = 8 * 2 = 16，此时数组变为 [14]。由于此时数组剩余元素为 1 个，因此返回数组首元素 14

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lastRemaining(int n) {
        boolean isFromLeft = true;
        int head = 1;
        int step = 1;
        while (n > 1) {
            if (isFromLeft) {
                head = head + step;
                isFromLeft = false;
            } else {
                if (n % 2 == 1) {
                    head = head + step;
                }
                isFromLeft = true;
            }
            
            step = step * 2;
            n = n / 2;
        }
        
        return head;
    }
}

参考资料

https://leetcode.com/problems/elimination-game/solutions/87119/JAVA:-Easiest-solution-O(logN)-with-explanation/