魔术排列

难度: Medium

秋日市集上，魔术师邀请小扣与他互动。魔术师的道具为分别写有数字 `1~N` 的 `N` 张卡牌，然后请小扣思考一个 `N` 张卡牌的排列 `target`。魔术师的目标是找到一个数字 k（k >= 1），使得初始排列顺序为 `1~N` 的卡牌经过特殊的洗牌方式最终变成小扣所想的排列 `target`，特殊的洗牌方式为： - 第一步，魔术师将当前位于 **偶数位置** 的卡牌（下标自 1 开始），保持 **当前排列顺序** 放在位于 **奇数位置** 的卡牌之前。例如：将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前，排列变为 [2,4,1,3,5]； - 第二步，若当前卡牌数量小于等于 `k`，则魔术师按排列顺序取走全部卡牌；若当前卡牌数量大于 `k`，则取走前 `k` 张卡牌，剩余卡牌继续重复这两个步骤，直至所有卡牌全部被取走；卡牌按照魔术师取走顺序构成的新排列为「魔术取数排列」，请返回是否存在这个数字 k 使得「魔术取数排列」恰好就是 `target`，从而让小扣感到大吃一惊。 **示例 1：** >输入：`target = [2,4,3,1,5]` > >输出：`true` > >解释：排列 target 长度为 5，初始排列为：1,2,3,4,5。我们选择 k = 2： >第一次：将当前排列 [1,2,3,4,5] 位于偶数位置的 [2,4] 置于奇数位置的 [1,3,5] 前，排列变为 [2,4,1,3,5]。取走前 2 张卡牌 2,4，剩余 [1,3,5]； >第二次：将当前排列 [1,3,5] 位于偶数位置的 [3] 置于奇数位置的 [1,5] 前，排列变为 [3,1,5]。取走前 2 张 3,1，剩余 [5]； >第三次：当前排列为 [5]，全部取出。 >最后，数字按照取出顺序构成的「魔术取数排列」2,4,3,1,5 恰好为 target。 **示例 2：** >输入：`target = [5,4,3,2,1]` > >输出：`false` > >解释：无法找到一个数字 k 可以使「魔术取数排列」恰好为 target。 **提示：** - `1 <= target.length = N <= 5000` - 题目保证 `target` 是 `1~N` 的一个排列。

Submission

运行时间: 28 ms

内存: 16.7 MB

class Solution:
    def isMagic(self, target: List[int]) -> bool:  
        # 这个东西的巧妙之处在于k值的判断
        n = len(target)
        if n == 1:
            return True
        
        nums = [i+1 for i in range(n)]
        first = nums[1::2] + nums[::2]
        k = 0
        while k < n and first[k] == target[k]:
            k += 1
        
        if k == 0:
            return False

        ans = []
        while nums:
            nums = nums[1::2] + nums[::2]
            ans.extend(nums[:k])
            nums = nums[k:]
        return ans == target

Explain

该题解通过首先确定可能的k值来检验是否可以通过特定的洗牌方法和取数顺序生成目标数组target。首先生成一个从1到N的数组，然后模拟魔术师的洗牌方法（将偶数位置的卡片放到奇数位置卡片的前面），以此来判定在第一次洗牌后的数组中，最长的和target数组前缀匹配的长度，即为k。接下来，使用这个k值，通过重复洗牌和截取操作来尝试构建一个和target相同的序列。如果通过这种方式完全构建的序列和target相同，返回true；否则，返回false。

时间复杂度: O(n log_k(n))

空间复杂度: O(n)

# 在类Solution内部定义的函数isMagic用于判断能否通过特定的k值生成目标数组target

class Solution:
    def isMagic(self, target: List[int]) -> bool:  # 定义函数, 参数为目标数组
        n = len(target)  # 获取数组长度
        if n == 1:  # 如果数组长度为1, 返回True
            return True
        
        nums = [i+1 for i in range(n)]  # 生成从1到n的数组
        first = nums[1::2] + nums[::2]  # 首次洗牌，偶数位置的数字放在前面
        k = 0
        while k < n and first[k] == target[k]:  # 确定k的值，即第一次洗牌后与目标数组匹配的最长前缀
            k += 1
        
        if k == 0:  # 如果k为0，说明没有匹配的前缀，返回False
            return False

        ans = []  # 用于存储最终生成的数组
        while nums:  # 当nums不为空时执行循环
            nums = nums[1::2] + nums[::2]  # 再次洗牌
            ans.extend(nums[:k])  # 取出前k个元素并加到ans中
            nums = nums[k:]  # 更新nums，去掉已经取出的元素
        return ans == target  # 比较最终生成的数组与目标数组是否一致，返回比较结果

Explore

在定义函数isMagic时，选择从1到N的顺序来初始化数组是基于题目设定和问题的自然性质。这种顺序代表了一个最自然的、未经处理的序列状态，即连续自然数的最初排列方式。此外，考虑到题目描述中未指明使用非标准初始排列，遵循这一自然顺序有助于简化问题并避免引入不必要的复杂性。实际上，使用其他初始排列可以作为探索或拓展问题的方式，但对于解决标准问题而言，从1到N的顺序是最直接和合适的选择。

在确定k值后，即在第一次洗牌后与target数组匹配的最长前缀长度，该值用于指导后续的洗牌和取数操作。在保证这个k值在后续过程中仍然有效的关键在于，算法的设计必须确保每次洗牌后都能从前k个元素中取出与target对应的元素。算法通过不断地洗牌和按k取数来尝试重建整个target数组。如果在任何一步中，从nums数组中取出的前k个元素无法与target中相应的部分匹配，则整个算法会终止并返回false。因此，k值的有效性是通过算法的控制流和循环中的条件检查来维持的。

当k值非常小，如k=1时，表明每次洗牌后只能从数组中取出一个元素来构建目标数组。在这种情况下，算法需要执行更多次的洗牌和取数操作来完成数组的构建，从而可能导致效率降低。具体来说，如果k=1，则每次洗牌后只取一个元素，这意味着为了构建长度为N的target数组，可能需要进行N次洗牌和取数操作。这显然比较高的k值（如接近N/2）需要更多的计算和时间，因此在k值较小的情况下，算法的效率较低，并可能显著影响性能。